@Proceedings{COLT2019,
title = {Proceedings of Machine Learning Research},
booktitle = {Proceedings of Machine Learning Research},
editor = {Alina Beygelzimer and Daniel Hsu},
publisher = {PMLR},
series = {Proceedings of Machine Learning Research},
volume = 99
}
@InProceedings{beygelzimer19a,
title = {Conference on Learning Theory 2019: Preface},
author = {Beygelzimer, Alina and Hsu, Daniel},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1--2},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/beygelzimer19a/beygelzimer19a.pdf},
url = {http://proceedings.mlr.press/v99/beygelzimer19a.html},
abstract = {Preface to the proceedings of the 32nd Conference on Learning Theory.}
}
@InProceedings{acharya19a,
title = {Inference under Information Constraints: Lower Bounds from Chi-Square Contraction},
author = {Acharya, Jayadev and Canonne, Cl{\'{e}}ment L and Tyagi, Himanshu},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {3--17},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/acharya19a/acharya19a.pdf},
url = {http://proceedings.mlr.press/v99/acharya19a.html},
abstract = {Multiple users getting one sample each from an unknown distribution seek to enable a central server to conduct statistical inference. However, each player can only provide limited amount of information about its sample to the server. We propose a unified framework to study such distributed inference problems under local information constraints. We model the local information constraints by a set of channels $\mathcal{W}$: each player chooses a channel from $\mathcal{W}$, and then passes their data through this channel before transmitting the output to the server. The goal in this distributed setting is to understand the blow-up in data requirement imposed by the information constraints, compared to the centralized setting where all data samples are available to the server. We introduce two notions of \emph{chi-square fluctuations} which provide bounds for the average distance and the distance to the average of a local perturbation. When information constraints are imposed, by the standard data-processing inequality, pairwise distances contract and so do our chi-square fluctuations. We provide a precise characterization of this contraction for discrete $k$-ary distributions and use it to obtain to general lower bounds for distribution learning and testing under information constraints. Our results involve notions of minmax and maxmin chi-square fluctuations, where the maximum is over the choice of channels and the minimum is over perturbations. The former emerges when considering public-coin protocols for testing and is bounded in terms of Frobenius norm of a positive semidefinite matrix $H$, a function of the channel family $\mathcal{W}$. The latter appears for private-coin protocols and is bounded by the nuclear norm of $H$ which is smaller than its Frobenius norm, establishing a separation between the sample complexity of testing using public and private coins.}
}
@InProceedings{agarwal19a,
title = {Learning in Non-convex Games with an Optimization Oracle},
author = {Agarwal, Naman and Gonen, Alon and Hazan, Elad},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {18--29},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/agarwal19a/agarwal19a.pdf},
url = {http://proceedings.mlr.press/v99/agarwal19a.html},
abstract = {We consider online learning in an adversarial, non-convex setting under the assumption that the learner has an access to an offline optimization oracle. In the general setting of prediction with expert advice, Hazan and Koren established that in the optimization-oracle model, online learning requires exponentially more computation than statistical learning. In this paper we show that by slightly strengthening the oracle model, the online and the statistical learning models become computationally equivalent. Our result holds for any Lipschitz and bounded (but not necessarily convex) function. As an application we demonstrate how the offline oracle enables efficient computation of an equilibrium in non-convex games, that include GAN (generative adversarial networks) as a special case.}
}
@InProceedings{alabi19a,
title = {Learning to Prune: Speeding up Repeated Computations},
author = {Alabi, Daniel and Kalai, Adam Tauman and Liggett, Katrina and Musco, Cameron and Tzamos, Christos and Vitercik, Ellen},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {30--33},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/alabi19a/alabi19a.pdf},
url = {http://proceedings.mlr.press/v99/alabi19a.html},
abstract = {Algorithms often must solve sequences of closely related problems. If the algorithm runs a standard procedure with worst-case runtime guarantees on each instance, it will fail to take advantage of valuable structure shared across the problem instances. When a commuter drives from work to home, for example, there are typically only a handful of routes that will ever be the shortest path. A naïve algorithm that does not exploit this common structure may spend most of its time checking roads that will never be in the shortest path. More generally, we can often ignore large swaths of the search space that will likely never contain an optimal solution. We present an algorithm that learns to maximally prune the search space on repeated computations, thereby reducing runtime while provably outputting the correct solution each period with high probability. Our algorithm employs a simple explore-exploit technique resembling those used in online algorithms, though our setting is quite different. We prove that, with respect to our model of pruning search spaces, our approach is optimal up to constant factors. Finally, we illustrate the applicability of our model and algorithm to three classic problems: shortest-path routing, string search, and linear programming. We present experiments confirming that our simple algorithm is effective at significantly reducing the runtime of solving repeated computations.}
}
@InProceedings{aliakbarpour19a,
title = {Towards Testing Monotonicity of Distributions Over General Posets},
author = {Aliakbarpour, Maryam and Gouleakis, Themis and Peebles, John and Rubinfeld, Ronitt and Yodpinyanee, Anak},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {34--82},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/aliakbarpour19a/aliakbarpour19a.pdf},
url = {http://proceedings.mlr.press/v99/aliakbarpour19a.html},
abstract = {In this work, we consider the sample complexity required for testing the monotonicity of distributions over partial orders. A distribution $p$ over a poset is {\em monotone} if, for any pair of domain elements $x$ and $y$ such that $x \preceq y$, $p(x) \leq p(y)$. To understand the sample complexity of this problem, we introduce a new property called \emph{bigness} over a finite domain, where the distribution is $T$-big if the minimum probability for any domain element is at least $T$. We establish a lower bound of $\Omega(n/\log n)$ for testing bigness of distributions on domains of size $n$. We then build on these lower bounds to give $\Omega(n/\log{n})$ lower bounds for testing monotonicity over a matching poset of size $n$ and significantly improved lower bounds over the hypercube poset. We give sublinear sample complexity bounds for testing bigness and for testing monotonicity over the matching poset. We then give a number of tools for analyzing upper bounds on the sample complexity of the monotonicity testing problem. }
}
@InProceedings{aliakbarpour19b,
title = {Testing Mixtures of Discrete Distributions},
author = {Aliakbarpour, Maryam and Kumar, Ravi and Rubinfeld, Ronitt},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {83--114},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/aliakbarpour19b/aliakbarpour19b.pdf},
url = {http://proceedings.mlr.press/v99/aliakbarpour19b.html},
abstract = { There has been significant study on the sample complexity of testing properties of distributions over large domains. For many properties, it is known that the sample complexity can be substantially smaller than the domain size. For example, over a domain of size $n$, distinguishing the uniform distribution from distributions that are far from uniform in $\ell_1$-distance uses only $O(\sqrt{n})$ samples. However, the picture is very different in the presence of arbitrary noise, even when the amount of noise is quite small. In this case, one must distinguish if samples are coming from a distribution that is $\epsilon$-close to uniform from the case where the distribution is $(1-\epsilon)$-far from uniform. The latter task requires nearly linear in $n$ samples (Valiant, 2008; Valiant and Valiant, 2017a). In this work, we present a noise model that on one hand is more tractable for the testing problem, and on the other hand represents a rich class of noise families. In our model, the noisy distribution is a mixture of the original distribution and noise, where the latter is known to the tester either explicitly or via sample access; the form of the noise is also known \emph{a priori}. Focusing on the identity and closeness testing problems leads to the following mixture testing question: Given samples of distributions $p, q_1,q_2$, can we test if $p$ is a mixture of $q_1$ and $q_2$? We consider this general question in various scenarios that differ in terms of how the tester can access the distributions, and show that indeed this problem is more tractable. Our results show that the sample complexity of our testers are exactly the same as for the classical non-mixture case. }
}
@InProceedings{anastasiou19a,
title = {Normal Approximation for Stochastic Gradient Descent via Non-Asymptotic Rates of Martingale CLT},
author = {Anastasiou, Andreas and Balasubramanian, Krishnakumar and Erdogdu, Murat A.},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {115--137},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/anastasiou19a/anastasiou19a.pdf},
url = {http://proceedings.mlr.press/v99/anastasiou19a.html},
abstract = {We provide non-asymptotic convergence rates of the Polyak-Ruppert averaged stochastic gradient descent (SGD) to a normal random vector for a class of twice-differentiable test functions. A crucial intermediate step is proving a non-asymptotic martingale central limit theorem (CLT), i.e., establishing the rates of convergence of a multivariate martingale difference sequence to a normal random vector, which might be of independent interest. We obtain the explicit rates for the multivariate martingale CLT using a combination of Stein?s method and Lindeberg?s argument, which is then used in conjunction with a non-asymptotic analysis of averaged SGD proposed in [PJ92]. Our results have potentially interesting consequences for computing confidence intervals for parameter estimation with SGD and constructing hypothesis tests with SGD that are valid in a non-asymptotic sense}
}
@InProceedings{auer19a,
title = {Adaptively Tracking the Best Bandit Arm with an Unknown Number of Distribution Changes},
author = {Auer, Peter and Gajane, Pratik and Ortner, Ronald},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {138--158},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/auer19a/auer19a.pdf},
url = {http://proceedings.mlr.press/v99/auer19a.html},
abstract = {We consider the variant of the stochastic multi-armed bandit problem where the stochastic reward distributions may change abruptly several times. In contrast to previous work, we are able to achieve (nearly) optimal mini-max regret bounds without knowing the number of changes. For this setting, we propose an algorithm called ADSWITCH and provide performance guarantees for the regret evaluated against the optimal non-stationary policy. Our regret bound is the first optimal bound for an algorithm that is not tuned with respect to the number of changes.}
}
@InProceedings{auer19b,
title = {Achieving Optimal Dynamic Regret for Non-stationary Bandits without Prior Information},
author = {Auer, Peter and Chen, Yifang and Gajane, Pratik and Lee, Chung-Wei and Luo, Haipeng and Ortner, Ronald and Wei, Chen-Yu},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {159--163},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/auer19b/auer19b.pdf},
url = {http://proceedings.mlr.press/v99/auer19b.html},
abstract = {This joint extended abstract introduces and compares the results of (Auer et al., 2019) and (Chen et al., 2019), both of which resolve the problem of achieving optimal dynamic regret for non-stationary bandits without prior information on the non-stationarity. Specifically, Auer et al. (2019) resolve the problem for the traditional multi-armed bandits setting, while Chen et al. (2019) give a solution for the more general contextual bandits setting. Both works extend the key idea of (Auer et al., 2018) developed for a simpler two-armed setting.}
}
@InProceedings{bach19a,
title = {A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noise},
author = {Bach, Francis and Levy, Kfir Y},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {164--194},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/bach19a/bach19a.pdf},
url = {http://proceedings.mlr.press/v99/bach19a.html},
abstract = {We consider variational inequalities coming from monotone operators, a setting that includes convex minimization and convex-concave saddle-point problems. We assume an access to potentially noisy unbiased values of the monotone operators and assess convergence through a compatible gap function which corresponds to the standard optimality criteria in the aforementioned subcases. We present a universal algorithm for these inequalities based on the Mirror-Prox algorithm. Concretely, our algorithm \emph{simultaneously} achieves the optimal rates for the smooth/non-smooth, and noisy/noiseless settings. This is done without any prior knowledge of these properties, and in the general set-up of arbitrary norms and compatible Bregman divergences. For convex minimization and convex-concave saddle-point problems, this leads to new adaptive algorithms. Our method relies on a novel yet simple adaptive choice of the step-size, which can be seen as the appropriate extension of AdaGrad to handle constrained problems.}
}
@InProceedings{bakshi19a,
title = {Learning Two Layer Rectified Neural Networks in Polynomial Time},
author = {Bakshi, Ainesh and Jayaram, Rajesh and Woodruff, David P},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {195--268},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/bakshi19a/bakshi19a.pdf},
url = {http://proceedings.mlr.press/v99/bakshi19a.html},
abstract = {We consider the following fundamental problem in the study of neural networks: given input examples $x \in \mathbb{R}^d$ and their vector-valued labels, as defined by an underlying generative neural network, recover the weight matrices of this network. We consider two-layer networks, mapping $\mathbb{R}^d$ to $\mathbb{R}^m$, with a single hidden layer and $k$ non-linear activation units $f(\cdot)$, where $f(x) = \max \{x , 0\}$ is the ReLU activation function. Such a network is specified by two weight matrices, $\mathbf{U}^* \in \mathbb{R}^{m \times k}, \mathbf{V}^* \in \mathbb{R}^{k \times d}$, such that the label of an example $x \in \mathbb{R}^{d}$ is given by $\mathbf{U}^* f(\mathbf{V}^* x)$, where $f(\cdot)$ is applied coordinate-wise. Given $n$ samples $x^1,…,x^n \in \mathbb{R}^d$ as a matrix $\mathbf{X} \in \mathbb{R}^{d \times n}$ and the label $\mathbf{U}^* f(\mathbf{V}^* \mathbf{X})$ of the network on these samples, our goal is to recover the weight matrices $\mathbf{U}^*$ and $\mathbf{V}^*$. More generally, our labels $\mathbf{U}^* f(\mathbf{V}^* \mathbf{X})$ may be corrupted by noise, and instead we observe $\mathbf{U}^* f(\mathbf{V}^* \mathbf{X}) + \mathbf{E}$ where $\mathbf{E}$ is some noise matrix. Even in this case, we may still be interested in recovering good approximations to the weight matrices $\mathbf{U}^*$ and $\mathbf{V}^*$. In this work, we develop algorithms and hardness results under varying assumptions on the input and noise. Although the problem is NP-hard even for $k=2$, by assuming Gaussian marginals over the input $\mathbf{X}$ we are able to develop polynomial time algorithms for the approximate recovery of $\mathbf{U}^*$ and $\mathbf{V}^*$. Perhaps surprisingly, in the noiseless case our algorithms recover $\mathbf{U}^*,\mathbf{V}^*$ \textit{exactly}, i.e. with no error, in \textit{strongly} polynomial time. To the best of the our knowledge, this is the first algorithm to accomplish exact recovery for the ReLU activation function. For the noisy case, we give the first polynomial time algorithm that approximately recovers the weights in the presence of mean-zero noise $\mathbf{E}$. Our algorithms generalize to a larger class of \textit{rectified} activation functions, $f(x) = 0$ when $x\leq 0$, and $f(x) > 0$ otherwise. Although our polynomial time results require $\mathbf{U}^*$ to have full column rank, we also give a fixed-parameter tractable algorithm (in $k$) when $\mathbf{U}^*$ does not have this property. Lastly, we give a fixed-parameter tractable algorithm for more arbitrary noise matrices $\mathbf{E}$, so long as they are independent of $\mathbf{X}$.}
}
@InProceedings{beimel19a,
title = {Private Center Points and Learning of Halfspaces},
author = {Beimel, Amos and and Moran, Shay and Nissim, Kobbi and Stemmer, Uri},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {269--282},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/beimel19a/beimel19a.pdf},
url = {http://proceedings.mlr.press/v99/beimel19a.html},
abstract = { We present a private agnostic learner for halfspaces over an arbitrary finite domain $X\subset \R^d$ with sample complexity $\mathsf{poly}(d,2^{\log^*|X|})$. The building block for this learner is a differentially private algorithm for locating an approximate center point of $m>\mathsf{poly}(d,2^{\log^*|X|})$ points – a high dimensional generalization of the median function. Our construction establishes a relationship between these two problems that is reminiscent of the relation between the median and learning one-dimensional thresholds [Bun et al. FOCS ’15]. This relationship suggests that the problem of privately locating a center point may have further applications in the design of differentially private algorithms. We also provide a lower bound on the sample complexity for privately finding a point in the convex hull. For approximate differential privacy, we show a lower bound of $m=\Omega(d+\log^*|X|)$, whereas for pure differential privacy $m=\Omega(d\log|X|)$. }
}
@InProceedings{bezakova19a,
title = {Lower bounds for testing graphical models: colorings and antiferromagnetic {I}sing models},
author = {Bez\'akov\'a, Ivona and Blanca, Antonio and Chen, Zongchen and {\v{S}}tefankovi{\v{c}}, Daniel and Vigoda, Eric},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {283--298},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/bezakova19a/bezakova19a.pdf},
url = {http://proceedings.mlr.press/v99/bezakova19a.html},
abstract = { We study the identity testing problem in the context of spin systems or undirected graphical models, where it takes the following form: given the parameter specification of the model $M$ and a sampling oracle for the distribution $\mu_{M^*}$ of an unknown model $M^*$, can we efficiently determine if the two models $M$ and $M^*$ are the same? We consider identity testing for both soft-constraint and hard-constraint systems. In particular, we prove hardness results in two prototypical cases, the \emph{Ising model} and \emph{proper colorings}, and explore whether identity testing is easier than structure learning. For the ferromagnetic (attractive) Ising model, Daskalasis et al. (2018) presented a polynomial time algorithm for identity testing. We prove hardness results in the antiferromagnetic (repulsive) setting in the same regime of parameters where structure learning is known to require a super-polynomial number of samples. Specifically, for $n$-vertex graphs of maximum degree $d$, we prove that if $|\beta| d = \omega(\log{n})$ (where $\beta$ is the inverse temperature parameter), then there is no identity testing algorithm for the antiferromagnetic Ising model that runs in polynomial time unless $RP\!=\!NP$. We also establish computational lower bounds for a broader set of parameters under the (randomized) exponential time hypothesis. In our proofs, we use random graphs as gadgets; this is inspired by similar constructions in seminal works on the hardness of approximate counting. In the hard-constraint setting, we present hardness results for identity testing for proper colorings. Our results are based on the presumed hardness of \textsc{#BIS}, the problem of (approximately) counting independent sets in bipartite graphs. In particular, we prove that identity testing for colorings is hard in the same range of parameters where structure learning is known to be hard, which in turn matches the parameter regime for NP-hardness of the corresponding decision problem. }
}
@InProceedings{bhaskara19a,
title = {{Approximate Guarantees for Dictionary Learning}},
author = {Bhaskara, Aditya and Tai, Wai Ming},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {299--317},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/bhaskara19a/bhaskara19a.pdf},
url = {http://proceedings.mlr.press/v99/bhaskara19a.html},
abstract = {In the dictionary learning (or sparse coding) problem, we are given a collection of signals (vectors in $\mathbb{R}^d$), and the goal is to find a "basis" in which the signals have a sparse (approximate) representation. The problem has received a lot of attention in signal processing, learning, and theoretical computer science. The problem is formalized as factorizing a matrix $X (d \times n)$ (whose columns are the signals) as $X = AY$, where $A$ has a prescribed number $m$ of columns (typically $m \ll n$), and $Y$ has columns that are $k$-sparse (typically $k \ll d$). Most of the known theoretical results involve assuming that the columns of the unknown $A$ have certain incoherence properties, and that the coefficient matrix $Y$ has random (or partly random) structure. The goal of our work is to understand what can be said in the absence of such assumptions. Can we still find $A$ and $Y$ such that $X \approx AY$? We show that this is possible, if we allow violating the bounds on $m$ and $k$ by appropriate factors that depend on $k$ and the desired approximation. Our results rely on an algorithm for what we call the threshold correlation problem, which turns out to be related to hypercontractive norms of matrices. We also show that our algorithmic ideas apply to a setting in which some of the columns of $X$ are outliers, thus giving similar guarantees even in this challenging setting.}
}
@InProceedings{bousquet19a,
title = {The Optimal Approximation Factor in Density Estimation},
author = {Bousquet, Olivier and Kane, Daniel and Moran, Shay},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {318--341},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/bousquet19a/bousquet19a.pdf},
url = {http://proceedings.mlr.press/v99/bousquet19a.html},
abstract = { Consider the following problem: given two arbitrary densities $q_1,q_2$ and a sample-access to an unknown target density $p$, find which of the $q_i$’s is closer to $p$ in total variation. A remarkable result due to Yatracos shows that this problem is tractable in the following sense: there exists an algorithm that uses $O(\epsilon^{-2})$ samples from $p$ and outputs $q_i$ such that with high probability, $TV(q_i,p) \leq 3\cdot OPT + \epsilon$, where $OPT= \min\{TV(q_1,p),TV(q_2,p)\}$. Moreover, this result extends to any finite class of densities $\mathcal{Q}$: there exists an algorithm that outputs the best density in $\mathcal{Q}$ up to a multiplicative approximation factor of 3. We complement and extend this result by showing that: (i) the factor 3 can not be improved if one restricts the algorithm to output a density from $\mathcal{Q}$, and (ii) if one allows the algorithm to output arbitrary densities (e.g. a mixture of densities from $\mathcal{Q}$), then the approximation factor can be reduced to 2, which is optimal. In particular this demonstrates an advantage of improper learning over proper in this setup. We develop two approaches to achieve the optimal approximation factor of $2$: an adaptive one and a static one. Both approaches are based on a geometric point of view of the problem and rely on estimating surrogate metrics to the total variation. Our sample complexity bounds exploit techniques from {\it Adaptive Data Analysis}.}
}
@InProceedings{braverman19a,
title = {Sorted Top-k in Rounds},
author = {Braverman, Mark and Mao, Jieming and Peres, Yuval},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {342--382},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/braverman19a/braverman19a.pdf},
url = {http://proceedings.mlr.press/v99/braverman19a.html},
abstract = { We consider the sorted top-$k$ problem whose goal is to recover the top-$k$ items with the correct order out of $n$ items using pairwise comparisons. In many applications, multiple rounds of interaction can be costly. We restrict our attention to algorithms with a constant number of rounds $r$ and try to minimize the sample complexity, i.e. the number of comparisons. When the comparisons are noiseless, we characterize how the optimal sample complexity depends on the number of rounds (up to a polylogarithmic factor for general $r$ and up to a constant factor for $r=1$ or 2). In particular, the sample complexity is $\Theta(n^2)$ for $r=1$, $\Theta(n\sqrt{k} + n^{4/3})$ for $r=2$ and $\tilde{\Theta}\left(n^{2/r} k^{(r-1)/r} + n\right)$ for $r \geq 3$. We extend our results of sorted top-$k$ to the noisy case where each comparison is correct with probability $2/3$. When $r=1$ or 2, we show that the sample complexity gets an extra $\Theta(\log(k))$ factor when we transition from the noiseless case to the noisy case. We also prove new results for top-$k$ and sorting in the noisy case. We believe our techniques can be generally useful for understanding the trade-off between round complexities and sample complexities of rank aggregation problems.}
}
@InProceedings{braverman19b,
title = {Multi-armed Bandit Problems with Strategic Arms},
author = {Braverman, Mark and Mao, Jieming and Schneider, Jon and Weinberg, S. Matthew},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {383--416},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/braverman19b/braverman19b.pdf},
url = {http://proceedings.mlr.press/v99/braverman19b.html},
abstract = { We study a strategic version of the multi-armed bandit problem, where each arm is an individual strategic agent and we, the principal, pull one arm each round. When pulled, the arm receives some private reward $v_a$ and can choose an amount $x_a$ to pass on to the principal (keeping $v_a-x_a$ for itself). All non-pulled arms get reward $0$. Each strategic arm tries to maximize its own utility over the course of $T$ rounds. Our goal is to design an algorithm for the principal incentivizing these arms to pass on as much of their private rewards as possible. When private rewards are stochastically drawn each round ($v_a^t \leftarrow D_a$), we show that: \begin{itemize} \item Algorithms that perform well in the classic adversarial multi-armed bandit setting necessarily perform poorly: For all algorithms that guarantee low regret in an adversarial setting, there exist distributions $D_1,\ldots,D_k$ and an $o(T)$-approximate Nash equilibrium for the arms where the principal receives reward $o(T)$. \item There exists an algorithm for the principal that induces a game among the arms where each arm has a dominant strategy. Moreover, for every $o(T)$-approximate Nash equilibrium, the principal receives expected reward $\mu’T - o(T)$, where $\mu’$ is the second-largest of the means $\mathbb{E}[D_{a}]$. This algorithm maintains its guarantee if the arms are non-strategic ($x_a = v_a$), and also if there is a mix of strategic and non-strategic arms. \end{itemize}}
}
@InProceedings{brennan19a,
title = {Universality of Computational Lower Bounds for Submatrix Detection},
author = {Brennan, Matthew and Bresler, Guy and Huleihel, Wasim},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {417--468},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/brennan19a/brennan19a.pdf},
url = {http://proceedings.mlr.press/v99/brennan19a.html},
abstract = {In the general submatrix detection problem, the task is to detect the presence of a small $k \times k$ submatrix with entries sampled from a distribution $\mathcal{P}$ in an $n \times n$ matrix of samples from $\mathcal{Q}$. This formulation includes a number of well-studied problems, such as biclustering when $\mathcal{P}$ and $\mathcal{Q}$ are Gaussians and the planted dense subgraph formulation of community detection when the submatrix is a principal minor and $\mathcal{P}$ and $\mathcal{Q}$ are Bernoulli random variables. These problems all seem to exhibit a universal phenomenon: there is a statistical-computational gap depending on $\mathcal{P}$ and $\mathcal{Q}$ between the minimum $k$ at which this task can be solved and the minimum $k$ at which it can be solved in polynomial time. Our main result is to tightly characterize this computational barrier as a tradeoff between $k$ and the KL divergences between $\mathcal{P}$ and $\mathcal{Q}$ through average-case reductions from the planted clique conjecture. These computational lower bounds hold given mild assumptions on $\mathcal{P}$ and $\mathcal{Q}$ arising naturally from classical binary hypothesis testing. Our results recover and generalize the planted clique lower bounds for Gaussian biclustering in Ma and Wu (2015) and Brennan et al. (2018) and for the sparse and general regimes of planted dense subgraph in Hajek et al. (2015) and Brennan et al. (2018). This yields the first universality principle for computational lower bounds obtained through average-case reductions.}
}
@InProceedings{brennan19b,
title = {Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness},
author = {Brennan, Matthew and Bresler, Guy},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {469--470},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/brennan19b/brennan19b.pdf},
url = {http://proceedings.mlr.press/v99/brennan19b.html},
abstract = {In the past decade, sparse principal component analysis has emerged as an archetypal problem for illustrating statistical-computational tradeoffs. This trend has largely been driven by a line of research aiming to characterize the average-case complexity of sparse PCA through reductions from the planted clique ($\textsc{pc}$) conjecture. All previous reductions either fail to show tight computational lower bounds matching existing algorithms or show lower bounds for formulations of sparse PCA other than its canonical generative model, the spiked covariance model. Also, these lower bounds all quickly degrade given weak forms of the $\textsc{pc}$ conjecture. We give a reduction from $\textsc{pc}$ that yields the first full characterization of the computational barrier in the spiked covariance model, providing tight lower bounds at all sparsities $k$. We also show the surprising result that even a mild improvement in the signal strength needed by the best known polynomial-time sparse PCA algorithms would imply that the hardness threshold for $\textsc{pc}$ is $\text{polylog}(N)$, rather than on the order $N^{1/2}$ as is widely conjectured. This is the first instance of a suboptimal hardness assumption implying optimal lower bounds for another problem in unsupervised learning.}
}
@InProceedings{brunel19a,
title = {Learning rates for Gaussian mixtures under group action},
author = {Brunel, Victor-Emmanuel},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {471--491},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/brunel19a/brunel19a.pdf},
url = {http://proceedings.mlr.press/v99/brunel19a.html},
abstract = {We study the pointwise maximum likelihood estimation rates for a class of Gaussian mixtures that are invariant under the action of some isometry group. This model is also known as multi-reference alignment, where random rotations of a given vector are observed, up to Gaussian noise. We completely characterize the speed of the maximum likelihood estimator, by giving a comprehensive description of the likelihood geometry of the model. We show that the unknown parameter can always be decomposed into two components, one of which can be estimated at the fast rate $n^{-1/2}$, the other one being estimated at the slower rate $n^{-1/4}$. We provide an algebraic description and a geometric interpretation of these facts.}
}
@InProceedings{bubeck19a,
title = {Near-optimal method for highly smooth convex optimization},
author = {Bubeck, S{\'e}bastien and Jiang, Qijia and Lee, Yin Tat and Li, Yuanzhi and Sidford, Aaron},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {492--507},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/bubeck19a/bubeck19a.pdf},
url = {http://proceedings.mlr.press/v99/bubeck19a.html},
abstract = {We propose a near-optimal method for highly smooth convex optimization. More precisely, in the oracle model where one obtains the $p^{th}$ order Taylor expansion of a function at the query point, we propose a method with rate of convergence $\tilde{O}(1/k^{\frac{ 3p +1}{2}})$ after $k$ queries to the oracle for any convex function whose $p^{th}$ order derivative is Lipschitz.}
}
@InProceedings{bubeck19b,
title = {Improved Path-length Regret Bounds for Bandits},
author = {Bubeck, S{\'e}bastien and Li, Yuanzhi and Luo, Haipeng and Wei, Chen-Yu},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {508--528},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/bubeck19b/bubeck19b.pdf},
url = {http://proceedings.mlr.press/v99/bubeck19b.html},
abstract = {We study adaptive regret bounds in terms of the variation of the losses (the so-called path-length bounds) for both multi-armed bandit and more generally linear bandit. We first show that the seemingly suboptimal path-length bound of (Wei and Luo, 2018) is in fact not improvable for adaptive adversary. Despite this negative result, we then develop two new algorithms, one that strictly improves over (Wei and Luo, 2018) with a smaller path-length measure, and the other which improves over (Wei and Luo, 2018) for oblivious adversary when the path-length is large. Our algorithms are based on the well-studied optimistic mirror descent framework, but importantly with several novel techniques, including new optimistic predictions, a slight bias towards recently selected arms, and the use of a hybrid regularizer similar to that of (Bubeck et al., 2018). Furthermore, we extend our results to linear bandit by showing a reduction to obtaining dynamic regret for a full-information problem, followed by a further reduction to convex body chasing. As a consequence we obtain new dynamic regret results as well as the first path-length regret bounds for general linear bandit.}
}
@InProceedings{busa-fekete19a,
title = {Optimal Learning of Mallows Block Model},
author = {Busa-Fekete, Robert and Fotakis, Dimitris and Sz\"{o}r\'enyi, Bal\'{a}zs and Zampetakis, Manolis},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {529--532},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/busa-fekete19a/busa-fekete19a.pdf},
url = {http://proceedings.mlr.press/v99/busa-fekete19a.html},
abstract = {The Mallows model, introduced in the seminal paper of Mallows 1957, is one of the most fundamental ranking distribution over the symmetric group $S_m$. To analyze more complex ranking data, several studies considered the Generalized Mallows model defined by Fligner and Verducci 1986. Despite the significant research interest of ranking distributions, the exact sample complexity of estimating the parameters of a Mallows and a Generalized Mallows Model is not well-understood. The main result of the paper is a tight sample complexity bound for learning Mallows and Generalized Mallows Model. We approach the learning problem by analyzing a more general model which interpolates between the single parameter Mallows Model and the $m$ parameter Mallows model. We call our model Mallows Block Model – referring to the Block Models that are a popular model in theoretical statistics. Our sample complexity analysis gives tight bound for learning the Mallows Block Model for any number of blocks. We provide essentially matching lower bounds for our sample complexity results. As a corollary of our analysis, it turns out that, if the central ranking is known, one single sample from the Mallows Block Model is sufficient to estimate the spread parameters with error that goes to zero as the size of the permutations goes to infinity. In addition, we calculate the exact rate of the parameter estimation error.}
}
@InProceedings{calandriello19a,
title = {Gaussian Process Optimization with Adaptive Sketching: Scalable and No Regret},
author = {Calandriello, Daniele and Carratino, Luigi and Lazaric, Alessandro and Valko, Michal and Rosasco, Lorenzo},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {533--557},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/calandriello19a/calandriello19a.pdf},
url = {http://proceedings.mlr.press/v99/calandriello19a.html},
abstract = { Gaussian processes (GP) are a stochastic processes, used as Bayesian approach for the optimization of black-box functions. Despite their effectiveness in simple problems, GP-based algorithms hardly scale to high-dimensional functions, as their per-iteration time and space cost is at least \emph{quadratic} in the number of dimensions $d$ and iterations $t$. Given a set of $A$ alternatives to choose from, the overall runtime $O(t^3 A)$ is prohibitive. In this paper, we introduce BKB (\textit{budgeted kernelized bandit}), a new approximate GP algorithm for optimization under bandit feedback that achieves near-optimal regret (and hence near-optimal convergence rate) with near-constant per-iteration complexity and remarkably no assumption on the input space or covariance of the GP. We combine a kernelized linear bandit algorithm (GP-UCB) leverage score sampling as a randomized matrix sketching and prove that selecting inducing points based on their posterior variance gives an accurate low-rank approximation of the GP, preserving variance estimates and confidence intervals. As a consequence, BKB does not suffer from \emph{variance starvation}, an important problem faced by many previous sparse GP approximations. Moreover, we show that our procedure selects at most $\widetilde{O}(d_{eff})$ points, where $d_{eff}$ is the \emph{effective} dimension of the explored space, which is typically much smaller than both $d$ and $t$. This greatly reduces the dimensionality of the problem, thus leading to a $O(T A d_{eff}^2)$ runtime and $O(A d_{eff})$ space complexity.}
}
@InProceedings{cao19a,
title = {Disagreement-Based Combinatorial Pure Exploration: Sample Complexity Bounds and an Efficient Algorithm},
author = {Cao, Tongyi and Krishnamurthy, Akshay},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {558--588},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/cao19a/cao19a.pdf},
url = {http://proceedings.mlr.press/v99/cao19a.html},
abstract = {We design new algorithms for the combinatorial pure exploration problem in the multi-arm bandit framework. In this problem, we are given $K$ distributions and a collection of subsets $\mathcal{V} \subset 2^{[K]}$ of these distributions, and we would like to find the subset $v \in \mathcal{V}$ that has largest mean, while collecting, in a sequential fashion, as few samples from the distributions as possible. In both the fixed budget and fixed confidence settings, our algorithms achieve new sample-complexity bounds that provide polynomial improvements on previous results in some settings. Via an information-theoretic lower bound, we show that no approach based on uniform sampling can improve on ours in any regime, yielding the first interactive algorithms for this problem with this basic property. Computationally, we show how to efficiently implement our fixed confidence algorithm whenever $\mathcal{V}$ supports efficient linear optimization. Our results involve precise concentration-of-measure arguments and a new algorithm for linear programming with exponentially many constraints.}
}
@InProceedings{carmon19a,
title = {A Rank-1 Sketch for Matrix Multiplicative Weights},
author = {Carmon, Yair and Duchi, John C and Aaron, Sidford and Kevin, Tian},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {589--623},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/carmon19a/carmon19a.pdf},
url = {http://proceedings.mlr.press/v99/carmon19a.html},
abstract = {We show that a simple randomized sketch of the matrix multiplicative weight (MMW) update enjoys (in expectation) the same regret bounds as MMW, up to a small constant factor. Unlike MMW, where every step requires full matrix exponentiation, our steps require only a single product of the form $e^A b$, which the Lanczos method approximates efficiently. Our key technique is to view the sketch as a \emph{randomized mirror projection}, and perform mirror descent analysis on the \emph{expected projection}. Our sketch solves the online eigenvector problem, improving the best known complexity bounds by $\Omega(\log^5 n)$. We also apply this sketch to semidefinite programming in saddle-point form, yielding a simple primal-dual scheme with guarantees matching the best in the literature.}
}
@InProceedings{chatziafratis19a,
title = {On the Computational Power of Online Gradient Descent},
author = {Chatziafratis, Vaggos and Roughgarden, Tim and Wang, Joshua R.},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {624--662},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/chatziafratis19a/chatziafratis19a.pdf},
url = {http://proceedings.mlr.press/v99/chatziafratis19a.html},
abstract = {We prove that the evolution of weight vectors in online gradient descent can encode arbitrary polynomial-space computations, even in very simple learning settings. Our results imply that, under weak complexity-theoretic assumptions, it is impossible to reason efficiently about the fine-grained behavior of online gradient descent.}
}
@InProceedings{chen19a,
title = {Active Regression via Linear-Sample Sparsification},
author = {Chen, Xue and Price, Eric},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {663--695},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/chen19a/chen19a.pdf},
url = {http://proceedings.mlr.press/v99/chen19a.html},
abstract = { We present an approach that improves the sample complexity for a variety of curve fitting problems, including active learning for linear regression, polynomial regression, and continuous sparse Fourier transforms. In the active linear regression problem, one would like to estimate the least squares solution $\beta^*$ minimizing $\|X\beta - y\|_2$ given the entire unlabeled dataset $X \in \mathbb{R}^{n \times d}$ but only observing a small number of labels $y_i$. We show that $O(d)$ labels suffice to find a constant factor approximation $\widetilde{\beta}$: \[ \mathbb{E}[\|{X} \widetilde{\beta} - y \|_2^2] \leq 2 \mathbb{E}[\|X \beta^* - y\|_2^2]. \]{This} improves on the best previous result of $O(d \log d)$ from leverage score sampling. We also present results for the \emph{inductive} setting, showing when $\widetilde{\beta}$ will generalize to fresh samples; these apply to continuous settings such as polynomial regression. Finally, we show how the techniques yield improved results for the non-linear sparse Fourier transform setting. }
}
@InProceedings{chen19b,
title = {A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal and Parameter-free},
author = {Chen, Yifang and Lee, Chung-Wei and Luo, Haipeng and Wei, Chen-Yu},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {696--726},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/chen19b/chen19b.pdf},
url = {http://proceedings.mlr.press/v99/chen19b.html},
abstract = {We propose the first contextual bandit algorithm that is parameter-free, efficient, and optimal in terms of dynamic regret. Specifically, our algorithm achieves $\mathcal{O}(\min\{\sqrt{KST}, K^{\frac{1}{3}}\Delta ^{\frac{1}{3}}T^{\frac{2}{3}}\})$ dynamic regret for a contextual bandit problem with $T$ rounds, $K$ actions, $S$ switches and $\Delta$ total variation in data distributions. Importantly, our algorithm is adaptive and does not need to know $S$ or $\Delta$ ahead of time, and can be implemented efficiently assuming access to an ERM oracle. Our results strictly improve the $\mathcal{O} (\min \{S^{\frac{1}{4}}T^{\frac{3}{4}}, \Delta^{\frac{1}{5}}T^{\frac{4}{5}}\})$ bound of (Luo et al., 2018), and greatly generalize and improve the $\mathcal{O}(\sqrt{ST})$ result of (Auer et al., 2018) that holds only for the two-armed bandit problem without contextual information. The key novelty of our algorithm is to introduce {\it replay phases}, in which the algorithm acts according to its previous decisions for a certain amount of time in order to detect non-stationarity while maintaining a good balance between exploration and exploitation.}
}
@InProceedings{cheng19a,
title = {Faster Algorithms for High-Dimensional Robust Covariance Estimation},
author = {Cheng, Yu and Diakonikolas, Ilias and Ge, Rong and Woodruff, David P.},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {727--757},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/cheng19a/cheng19a.pdf},
url = {http://proceedings.mlr.press/v99/cheng19a.html},
abstract = { We study the problem of estimating the covariance matrix of a high-dimensional distribution when a small constant fraction of the samples can be arbitrarily corrupted. Recent work gave the first polynomial time algorithms for this problem with near-optimal error guarantees for several natural structured distributions. Our main contribution is to develop faster algorithms for this problem whose running time nearly matches that of computing the empirical covariance. Given $N = \tilde{\Omega}(d^2/\epsilon^2)$ samples from a $d$-dimensional Gaussian distribution, an $\epsilon$-fraction of which may be arbitrarily corrupted, our algorithm runs in time $\tilde{O}(d^{3.26})/\mathrm{poly}(\epsilon)$ and approximates the unknown covariance matrix to optimal error up to a logarithmic factor. Previous robust algorithms with comparable error guarantees all have runtimes $\tilde{\Omega}(d^{2 \omega})$ when $\epsilon = \Omega(1)$, where $\omega$ is the exponent of matrix multiplication. We also provide evidence that improving the running time of our algorithm may require new algorithmic techniques. }
}
@InProceedings{cherapanamjeri19a,
title = {Testing Symmetric Markov Chains Without Hitting},
author = {Cherapanamjeri, Yeshwanth and Bartlett, Peter L.},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {758--785},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/cherapanamjeri19a/cherapanamjeri19a.pdf},
url = {http://proceedings.mlr.press/v99/cherapanamjeri19a.html},
abstract = {We study the problem of identity testing of symmetric markov chains. In this setting, we are given access to a single trajectory from a markov chain with unknown transition matrix $\bm{Q}$ and the goal is to determine whether $\bm{Q} = \bm{P}$ for some known matrix $\bm{P}$ or $\text{Dist}(\bm{P}, \bm{Q}) \geq \epsilon$ where $\text{Dist}$ is suitably defined. In recent work by Daskalakis et al, 2018, it was shown that it is possible to distinguish between the two cases provided the length of the observed trajectory is at least super-linear in the hitting time of $\bm{P}$ which may be arbitrarily large. In this paper, we propose an algorithm that avoids this dependence on hitting time thus enabling efficient testing of markov chains even in cases where it is infeasible to observe every state in the chain. Our algorithm is based on combining classical ideas from approximation algorithms with techniques for the spectral analysis of markov chains.}
}
@InProceedings{cherapanamjeri19b,
title = {Fast Mean Estimation with Sub-Gaussian Rates},
author = {Cherapanamjeri, Yeshwanth and Flammarion, Nicolas and Bartlett, Peter L.},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {786--806},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/cherapanamjeri19b/cherapanamjeri19b.pdf},
url = {http://proceedings.mlr.press/v99/cherapanamjeri19b.html},
abstract = {We propose an estimator for the mean of a random vector in $\mathbb{R}^d$ that can be computed in time $O(n^{3.5}+n^2d)$ for $n$ i.i.d. samples and that has error bounds matching the sub-Gaussian case. The only assumptions we make about the data distribution are that it has finite mean and covariance; in particular, we make no assumptions about higher-order moments. Like the polynomial time estimator introduced by Hopkins (2018), which is based on the sum-of-squares hierarchy, our estimator achieves optimal statistical efficiency in this challenging setting, but it has a significantly faster runtime and a simpler analysis.}
}
@InProceedings{cheung19a,
title = {Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Games},
author = {Cheung, Yun Kuen and Piliouras, Georgios},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {807--834},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/cheung19a/cheung19a.pdf},
url = {http://proceedings.mlr.press/v99/cheung19a.html},
abstract = {We establish that algorithmic experiments in zero-sum games “fail miserably” to confirm the unique, sharp prediction of maxmin equilibration. Contradicting nearly a century of economic thought that treats zero-sum games nearly axiomatically as the exemplar symbol of economic stability, we prove that no meaningful prediction can be made about the day-to-day behavior of online learning dynamics in zero-sum games. Concretely, Multiplicative Weights Updates (MWU) with constant step-size is \emph{Lyapunov chaotic} in the dual (payoff) space. Simply put, let’s assume that an observer asks the agents playing Matching-Pennies whether they prefer Heads or Tails (and by how much in terms of aggregate payoff so far). The range of possible answers consistent with any arbitrary small set of initial conditions blows up exponentially with time everywhere in the payoff space. This result is \emph{robust} both \emph{algorithmically} as well as \emph{game theoretically}. \textbf{Algorithmic robustness:} Chaos is robust to agents using any of a general sub-family of Follow-the-Regularized-Leader (FTRL) algorithms, the well known regret-minimizing dynamics, even when agents mix-and-match dynamics, use different or slowly decreasing step-sizes. \textbf{Game theoretic robustness:} Chaos is robust to all affine variants of zero-sum games (strictly competitive games), network variants with arbitrary large number of agents and even to competitive settings beyond these. Our result is in stark contrast with the time-average convergence of online learning to (approximate) Nash equilibrium, a result widely reported as “(weak) convergence to equilibrium”.}
}
@InProceedings{coester19a,
title = {Pure entropic regularization for metrical task systems},
author = {Coester, Christian and Lee, James R.},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {835--848},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/coester19a/coester19a.pdf},
url = {http://proceedings.mlr.press/v99/coester19a.html},
abstract = {We show that on every $n$-point HST metric, there is a randomized online algorithm for metrical task systems (MTS) that is $1$-competitive for service costs and $O(\log n)$-competitive for movement costs. In general, these refined guarantees are optimal up to the implicit constant. While an $O(\log n)$-competitive algorithm for MTS on HST metrics was developed by Bubeck et al. (2018), that approach could only establish an $O((\log n)^2)$-competitive ratio when the service costs are required to be $O(1)$-competitive. Our algorithm is an instantiation of online mirror descent with the regularizer derived from a multiscale conditional entropy. In fact, our algorithm satisfies a set of even more refined guarantees; we are able to exploit this property to combine it with known random embedding theorems and obtain, for {\em any} $n$-point metric space, a randomized algorithm that is $1$-competitive for service costs and $O((\log n)^2)$-competitive for movement costs.}
}
@InProceedings{cohen19a,
title = {A near-optimal algorithm for approximating the John Ellipsoid},
author = {Cohen, Michael B. and Cousins, Ben and Lee, Yin Tat and Yang, Xin},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {849--873},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/cohen19a/cohen19a.pdf},
url = {http://proceedings.mlr.press/v99/cohen19a.html},
abstract = {We develop a simple and efficient algorithm for approximating the John Ellipsoid of a symmetric polytope. Our algorithm is near optimal in the sense that our time complexity matches the current best verification algorithm. Experimental results suggest that our algorithm significantly outperforms existing algorithms. We also provide the MATLAB code for further research. }
}
@InProceedings{cutkosky19a,
title = {Artificial Constraints and Hints for Unbounded Online Learning},
author = {Cutkosky, Ashok},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {874--894},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/cutkosky19a/cutkosky19a.pdf},
url = {http://proceedings.mlr.press/v99/cutkosky19a.html},
abstract = {We provide algorithms that guarantees regret $R_T(u)\le \tilde O(G\|u\|^3 + G(\|u\|+1)\sqrt{T})$ or $R_T(u)\le \tilde O(G\|u\|^3T^{1/3} + GT^{1/3}+ G\|u\|\sqrt{T})$ for online convex optimization with $G$-Lipschitz losses for any comparison point $u$ without prior knowledge of either $G$ or $\|u\|$. Previous algorithms dispense with the $O(\|u\|^3)$ term at the expense of knowledge of one or both of these parameters, while a lower bound shows that some additional penalty term over $G\|u\|\sqrt{T}$ is necessary. Previous penalties were \emph{exponential} while our bounds are polynomial in all quantities. Further, given a known bound $\|u\|\le D$, our same techniques allow us to design algorithms that adapt optimally to the unknown value of $\|u\|$ without requiring knowledge of $G$.}
}
@InProceedings{cutkosky19b,
title = {Combining Online Learning Guarantees},
author = {Cutkosky, Ashok},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {895--913},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/cutkosky19b/cutkosky19b.pdf},
url = {http://proceedings.mlr.press/v99/cutkosky19b.html},
abstract = {We show how to take any two parameter-free online learning algorithms with different regret guarantees and obtain a single algorithm whose regret is the minimum of the two base algorithms. Our method is embarrassingly simple: just add the iterates. This trick can generate efficient algorithms that adapt to many norms simultaneously, as well as providing diagonal-style algorithms that still maintain dimension-free guarantees. We then proceed to show how a variant on this idea yields a black-box procedure for generating \emph{optimistic} online learning algorithms. This yields the first optimistic regret guarantees in the unconstrained setting and generically increases adaptivity. Further, our optimistic algorithms are guaranteed to do no worse than their non-optimistic counterparts regardless of the quality of the optimistic estimates provided to the algorithm.}
}
@InProceedings{dagan19a,
title = {Learning from Weakly Dependent Data under Dobrushin’s Condition},
author = {Dagan, Yuval and Daskalakis, Constantinos and Dikkala, Nishanth and Jayanti, Siddhartha},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {914--928},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/dagan19a/dagan19a.pdf},
url = {http://proceedings.mlr.press/v99/dagan19a.html},
abstract = {Statistical learning theory has largely focused on learning and generalization given independent and identically distributed (i.i.d.) samples. Motivated by applications involving time-series data, there has been a growing literature on learning and generalization in settings where data is sampled from an ergodic process. This work has also developed complexity measures, which appropriately extend the notion of Rademacher complexity to bound the generalization error and learning rates of hypothesis classes in this setting. Rather than time-series data, our work is motivated by settings where data is sampled on a network or a spatial domain, and thus do not fit well within the framework of prior work. We provide learning and generalization bounds for data that are complexly dependent, yet their distribution satisfies the standard Dobrushin’s condition. Indeed, we show that the standard complexity measures of Gaussian and Rademacher complexities and VC dimension are sufficient measures of complexity for the purposes of bounding the generalization error and learning rates of hypothesis classes in our setting. Moreover, our generalization bounds only degrade by constant factors compared to their i.i.d. analogs, and our learnability bounds degrade by log factors in the size of the training set.}
}
@InProceedings{dagan19b,
title = {Space lower bounds for linear prediction in the streaming model},
author = {Dagan, Yuval and Kur, Gil and Shamir, Ohad},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {929--954},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/dagan19b/dagan19b.pdf},
url = {http://proceedings.mlr.press/v99/dagan19b.html},
abstract = {We show that fundamental learning tasks, such as finding an approximate linear separator or linear regression, require memory at least \emph{quadratic} in the dimension, in a natural streaming setting. This implies that such problems cannot be solved (at least in this setting) by scalable memory-efficient streaming algorithms. Our results build on a memory lower bound for a simple linear-algebraic problem – finding approximate null vectors – and utilize the estimates on the packing of the Grassmannian, the manifold of all linear subspaces of fixed dimension. }
}
@InProceedings{daskalakis19a,
title = {Computationally and Statistically Efficient Truncated Regression},
author = {Daskalakis, Constantinos and Gouleakis, Themis and Tzamos, Christos and Zampetakis, Manolis},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {955--960},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/daskalakis19a/daskalakis19a.pdf},
url = {http://proceedings.mlr.press/v99/daskalakis19a.html},
abstract = { We provide a computationally and statistically efficient estimator for the classical problem of truncated linear regression, where the dependent variable $y = \vec{w}^{\rm T} \vec{x}+{\varepsilon}$ and its corresponding vector of covariates $\vec{x} \in \mathbb{R}^k$ are only revealed if the dependent variable falls in some subset $S \subseteq \mathbb{R}$; otherwise the existence of the pair $(\vec{x},y)$ is hidden. This problem has remained a challenge since the early works of Tobin 1958, Amemiya et al. 1973, HAusman et al 1977, Breen et al. 1996, its applications are abundant, and its history dates back even further to the work of Galton 1897, Pearson 1908, Lee 1915, and Fisher 1931. While consistent estimators of the regression coefficients have been identified, the error rates are not well-understood, especially in high-dimensional settings. Under a “thickness assumption” about the covariance matrix of the covariates in the revealed sample, we provide a computationally efficient estimator for the coefficient vector $\vec{w}$ from $n$ revealed samples that attains $\ell_2$ error $\tilde{O}(\sqrt{k / n})$, almost recovering the guarantees of least squares in the standard (untruncated) linear regression setting. Our estimator uses Projected Stochastic Gradient Descent (PSGD) on the negative log-likelihood of the truncated sample, and only needs oracle access to the set $S$, which may otherwise be arbitrary, and in particular may be non-convex. PSGD must be restricted to an appropriately defined convex cone to guarantee that the negative log-likelihood is strongly convex, which in turn is established using concentration of matrices on variables with sub-exponential tails. We perform experiments on simulated data to illustrate the accuracy of our estimator. As a corollary of our work, we show that SGD provably learns the parameters of single-layer neural networks with noisy Relu activation functions (see Nair and Hinton 2010, Bengio et al. 2013, Gulcehre et al. 2016), given linearly many, in the number of network parameters, input-output pairs in the realizable setting.}
}
@InProceedings{davies19a,
title = {Reconstructing Trees from Traces},
author = {Davies, Sami and Racz, Miklos Z. and Rashtchian, Cyrus},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {961--978},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/davies19a/davies19a.pdf},
url = {http://proceedings.mlr.press/v99/davies19a.html},
abstract = { We study the problem of learning a node-labeled tree given independent traces from an appropriately defined deletion channel. This problem, tree trace reconstruction, generalizes string trace reconstruction, which corresponds to the tree being a path. For many classes of trees, including complete trees and spiders, we provide algorithms that reconstruct the labels using only a polynomial number of traces. This exhibits a stark contrast to known results on string trace reconstruction, which require exponentially many traces, and where a central open problem is to determine whether a polynomial number of traces suffice. Our techniques combine novel combinatorial and complex analytic methods.}
}
@InProceedings{de19a,
title = {Is your function low dimensional?},
author = {De, Anindya and Mossel, Elchanan and Neeman, Joe},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {979--993},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/de19a/de19a.pdf},
url = {http://proceedings.mlr.press/v99/de19a.html},
abstract = {We study the problem of testing if a function depends on a small number of linear directions of its input data. We call a function $f$ a \emph{linear $k$-junta} if it is completely determined by some $k$-dimensional subspace of the input space. In this paper, we study the problem of testing whether a given $n$ variable function $f : \mathbb{R}^n \to \{0,1\}$, is a linear $k$-junta or $\epsilon$-far from all linear $k$-juntas, where the closeness is measured with respect to the Gaussian measure on $\mathbb{R}^n$. Linear $k$-juntas are a common generalization of two fundamental classes from Boolean function analysis (both of which have been studied in property testing) \textbf{1.} $k$- juntas which are functions on the Boolean cube which depend on at most k of the variables and \textbf{2.} intersection of $k$ halfspaces, a fundamental geometric concept class. We show that the class of linear $k$-juntas is not testable, but adding a surface area constraint makes it testable: we give a $\mathsf{poly}(k \cdot s/\epsilon)$-query non-adaptive tester for linear $k$-juntas with surface area at most $s$. We show that the polynomial dependence on $s$ is necessary. Moreover, we show that if the function is a linear $k$-junta with surface area at most $s$, we give a $(s \cdot k)^{O(k)}$-query non-adaptive algorithm to learn the function \emph{up to a rotation of the basis}. In particular, this implies that we can test the class of intersections of $k$ halfspaces in $\mathbb{R}^n$ with query complexity independent of $n$.}
}
@InProceedings{degwekar19a,
title = {Computational Limitations in Robust Classification and Win-Win Results},
author = {Degwekar, Akshay and Nakkiran, Preetum and Vaikuntanathan, Vinod},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {994--1028},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/degwekar19a/degwekar19a.pdf},
url = {http://proceedings.mlr.press/v99/degwekar19a.html},
abstract = {We continue the study of statistical/computational tradeoffs in learning robust classifiers, following the recent work of Bubeck, Lee, Price and Razenshteyn who showed examples of classification tasks where (a) an efficient robust classifier exists, in the small-perturbation regime; (b) a non-robust classifier can be learned efficiently; but (c) it is computationally hard to learn a robust classifier, assuming the hardness of factoring large numbers. Indeed, the question of whether a robust classifier for their task exists in the large perturbation regime seems related to important open questions in computational number theory. In this work, we extend their work in three directions. First, we demonstrate classification tasks where computationally efficient robust classification is impossible, even when computationally unbounded robust classifiers exist. For this, we rely on the existence of average-case hard functions, requiring no cryptographic assumptions. Second, we show hard-to-robustly-learn classification tasks in the large-perturbation regime. Namely, we show that even though an efficient classifier that is very robust (namely, tolerant to large perturbations) exists, it is computationally hard to learn any non-trivial robust classifier. Our first construction relies on the existence of one-way functions, a minimal assumption in cryptography, and the second on the hardness of the learning parity with noise problem. In the latter setting, not only does a non-robust classifier exist, but also an efficient algorithm that generates fresh new labeled samples given access to polynomially many training examples (termed as generation by Kearns et al. (1994)). Third, we show that any such counterexample implies the existence of cryptographic primitives such as one-way functions or even forms of public-key encryption. This leads us to a win-win scenario: either we can quickly learn an efficient robust classifier, or we can construct new instances of popular and useful cryptographic primitives.}
}
@InProceedings{derezinski19a,
title = {Fast determinantal point processes via distortion-free intermediate sampling},
author = {Derezi{\'n}ski, Micha{\l}},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1029--1049},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/derezinski19a/derezinski19a.pdf},
url = {http://proceedings.mlr.press/v99/derezinski19a.html},
abstract = { Given a fixed $n\times d$ matrix $\mathbf{X}$, where $n\gg d$, we study the complexity of sampling from a distribution over all subsets of rows where the probability of a subset is proportional to the squared volume of the parallelepiped spanned by the rows (a.k.a. a determinantal point process). In this task, it is important to minimize the preprocessing cost of the procedure (performed once) as well as the sampling cost (performed repeatedly). To that end, we propose a new determinantal point process algorithm which has the following two properties, both of which are novel: (1) a preprocessing step which runs in time $O\big(\text{number-of-non-zeros}(\mathbf{X})\cdot\log n\big)+\text{poly}(d)$, and (2) a sampling step which runs in $\text{poly}(d)$ time, independent of the number of rows $n$. We achieve this by introducing a new \textit{regularized} determinantal point process (R-DPP), which serves as an intermediate distribution in the sampling procedure by reducing the number of rows from $n$ to $\text{poly}(d)$. Crucially, this intermediate distribution does not distort the probabilities of the target sample. Our key novelty in defining the R-DPP is the use of a Poisson random variable for controlling the probabilities of different subset sizes, leading to new determinantal formulas such as the normalization constant for this distribution. Our algorithm has applications in many diverse areas where determinantal point processes have been used, such as machine learning, stochastic optimization, data summarization and low-rank matrix reconstruction.}
}
@InProceedings{derezinski19b,
title = {Minimax experimental design: Bridging the gap between statistical and worst-case approaches to least squares regression},
author = {Derezi{\'n}ski, Micha{\l} and Clarkson, Kenneth L. and Mahoney, Michael W. and Warmuth, Manfred K.},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1050--1069},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/derezinski19b/derezinski19b.pdf},
url = {http://proceedings.mlr.press/v99/derezinski19b.html},
abstract = {In experimental design, we are given a large collection of vectors, each with a hidden response value that we assume derives from an underlying linear model, and we wish to pick a small subset of the vectors such that querying the corresponding responses will lead to a good estimator of the model. A classical approach in statistics is to assume the responses are linear, plus zero-mean i.i.d. Gaussian noise, in which case the goal is to provide an unbiased estimator with smallest mean squared error (A-optimal design). A related approach, more common in computer science, is to assume the responses are arbitrary but fixed, in which case the goal is to estimate the least squares solution using few responses, as quickly as possible, for worst-case inputs. Despite many attempts, characterizing the relationship between these two approaches has proven elusive. We address this by proposing a framework for experimental design where the responses are produced by an arbitrary unknown distribution. We show that there is an efficient randomized experimental design procedure that achieves strong variance bounds for an unbiased estimator using few responses in this general model. Nearly tight bounds for the classical A-optimality criterion, as well as improved bounds for worst-case responses, emerge as special cases of this result. In the process, we develop a new algorithm for a joint sampling distribution called volume sampling, and we propose a new i.i.d. importance sampling method: inverse score sampling. A key novelty of our analysis is in developing new expected error bounds for worst-case regression by controlling the tail behavior of i.i.d. sampling via the jointness of volume sampling. Our result motivates a new minimax-optimality criterion for experimental design with unbiased estimators, which can be viewed as an extension of both A-optimal design and sampling for worst-case regression. }
}
@InProceedings{diakonikolas19a,
title = {Communication and Memory Efficient Testing of Discrete Distributions},
author = {Diakonikolas, Ilias and Gouleakis, Themis and Kane, Daniel M. and Rao, Sankeerth},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1070--1106},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/diakonikolas19a/diakonikolas19a.pdf},
url = {http://proceedings.mlr.press/v99/diakonikolas19a.html},
abstract = {We study distribution testing with communication and memory constraints in the following computational models: (1) The {\em one-pass streaming model} where the goal is to minimize the sample complexity of the protocol subject to a memory constraint, and (2) A {\em distributed model} where the data samples reside at multiple machines and the goal is to minimize the communication cost of the protocol. In both these models, we provide efficient algorithms for uniformity/identity testing (goodness of fit) and closeness testing (two sample testing). Moreover, we show nearly-tight lower bounds on (1) the sample complexity of any one-pass streaming tester for uniformity, subject to the memory constraint, and (2) the communication cost of any uniformity testing protocol, in a restricted “one-pass” model of communication.}
}
@InProceedings{diakonikolas19b,
title = {Testing Identity of Multidimensional Histograms},
author = {Diakonikolas, Ilias and Kane, Daniel M. and Peebles, John},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1107--1131},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/diakonikolas19b/diakonikolas19b.pdf},
url = {http://proceedings.mlr.press/v99/diakonikolas19b.html},
abstract = {We investigate the problem of identity testing for multidimensional histogram distributions. A distribution $p: D \to \mathbb{R}_+$, where $D \subseteq \mathbb{R}^d$, is called a $k$-histogram if there exists a partition of the domain into $k$ axis-aligned rectangles such that $p$ is constant within each such rectangle. Histograms are one of the most fundamental nonparametric families of distributions and have been extensively studied in computer science and statistics. We give the first identity tester for this problem with {\em sub-learning} sample complexity in any fixed dimension and a nearly-matching sample complexity lower bound. In more detail, let $q$ be an unknown $d$-dimensional $k$-histogram distribution in fixed dimension $d$, and $p$ be an explicitly given $d$-dimensional $k$-histogram. We want to correctly distinguish, with probability at least $2/3$, between the case that $p = q$ versus $\|p-q\|_1 \geq \epsilon$. We design an algorithm for this hypothesis testing problem with sample complexity $O((\sqrt{k}/\epsilon^2) 2^{d/2} \log^{2.5 d}(k/\epsilon))$ that runs in sample-polynomial time. Our algorithm is robust to model misspecification, i.e., succeeds even if $q$ is only promised to be {\em close} to a $k$-histogram. Moreover, for $k = 2^{\Omega(d)}$, we show a sample complexity lower bound of $(\sqrt{k}/\epsilon^2) \cdot \Omega(\log(k)/d)^{d-1}$ when $d\geq 2$. That is, for any fixed dimension $d$, our upper and lower bounds are nearly matching. Prior to our work, the sample complexity of the $d=1$ case was well-understood, but no algorithm with sub-learning sample complexity was known, even for $d=2$. Our new upper and lower bounds have interesting conceptual implications regarding the relation between learning and testing in this setting.}
}
@InProceedings{diakonikolas19c,
title = {Lower Bounds for Parallel and Randomized Convex Optimization},
author = {Diakonikolas, Jelena and Guzm\'{a}n, Crist\'{o}bal},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1132--1157},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/diakonikolas19c/diakonikolas19c.pdf},
url = {http://proceedings.mlr.press/v99/diakonikolas19c.html},
abstract = {We study the question of whether parallelization in the exploration of the feasible set can be used to speed up convex optimization, in the local oracle model of computation. We show that the answer is negative for both deterministic and randomized algorithms applied to essentially any of the interesting geometries and nonsmooth, weakly-smooth, or smooth objective functions. In particular, we show that it is not possible to obtain a polylogarithmic (in the sequential complexity of the problem) number of parallel rounds with a polynomial (in the dimension) number of queries per round. In the majority of these settings and when the dimension of the space is polynomial in the inverse target accuracy, our lower bounds match the oracle complexity of sequential convex optimization, up to at most a logarithmic factor in the dimension, which makes them (nearly) tight. Prior to our work, lower bounds for parallel convex optimization algorithms were only known in a small fraction of the settings considered in this paper, mainly applying to Euclidean ($\ell_2$) and $\ell_\infty$ spaces. Our work provides a more general and streamlined approach for proving lower bounds in the setting of parallel convex optimization. }
}
@InProceedings{dong19a,
title = {On the Performance of Thompson Sampling on Logistic Bandits},
author = {Dong, Shi and Ma, Tengyu and Van Roy, Benjamin},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1158--1160},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/dong19a/dong19a.pdf},
url = {http://proceedings.mlr.press/v99/dong19a.html},
abstract = {We study the logistic bandit, in which rewards are binary with success probability $\exp(\beta a^\top \theta) / (1 + \exp(\beta a^\top \theta))$ and actions $a$ and coefficients $\theta$ are within the $d$-dimensional unit ball. While prior regret bounds for algorithms that address the logistic bandit exhibit exponential dependence on the slope parameter $\beta$, we establish a regret bound for Thompson sampling that is independent of $\beta$. Specifically, we establish that, when the set of feasible actions is identical to the set of possible coefficient vectors, the Bayesian regret of Thompson sampling is $\tilde{O}(d\sqrt{T})$. We also establish a $\tilde{O}(\sqrt{d\eta T}/\Delta)$ bound that applies more broadly, where $\Delta$ is the worst-case optimal log-odds and $\eta$ is the “fragility dimension,” a new statistic we define to capture the degree to which an optimal action for one model fails to satisfice for others. We demonstrate that the fragility dimension plays an essential role by showing that, for any $\epsilon > 0$, no algorithm can achieve $\mathrm{poly}(d, 1/\Delta)\cdot T^{1-\epsilon}$ regret.}
}
@InProceedings{duchi19a,
title = {Lower Bounds for Locally Private Estimation via Communication Complexity},
author = {Duchi, John and Rogers, Ryan},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1161--1191},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/duchi19a/duchi19a.pdf},
url = {http://proceedings.mlr.press/v99/duchi19a.html},
abstract = {We develop lower bounds for estimation under local privacy constraints—including differential privacy and its relaxations to approximate or Rényi differential privacy—by showing an equivalence between private estimation and communication-restricted estimation problems. Our results apply to arbitrarily interactive privacy mechanisms, and they also give sharp lower bounds for all levels of differential privacy protections, that is, privacy mechanisms with privacy levels $\varepsilon \in [0, \infty)$. As a particular consequence of our results, we show that the minimax mean-squared error for estimating the mean of a bounded or Gaussian random vector in $d$ dimensions scales as $\frac{d}{n} \cdot \frac{d}{ \min\{\varepsilon, \varepsilon^2\}}$.}
}
@InProceedings{fang19a,
title = {Sharp Analysis for Nonconvex SGD Escaping from Saddle Points},
author = {Fang, Cong and Lin, Zhouchen and Zhang, Tong},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1192--1234},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/fang19a/fang19a.pdf},
url = {http://proceedings.mlr.press/v99/fang19a.html},
abstract = {In this paper, we give a sharp analysis for Stochastic Gradient Descent (SGD) and prove that SGD is able to efficiently escape from saddle points and find an $(\epsilon, O(\epsilon^{0.5}))$-approximate second-order stationary point in $\tilde{O}(\epsilon^{-3.5})$ stochastic gradient computations for generic nonconvex optimization problems, when the objective function satisfies gradient-Lipschitz, Hessian-Lipschitz, and dispersive noise assumptions. This result subverts the classical belief that SGD requires at least $O(\epsilon^{-4})$ stochastic gradient computations for obtaining an $(\epsilon,O(\epsilon^{0.5}))$-approximate second-order stationary point. Such SGD rate matches, up to a polylogarithmic factor of problem-dependent parameters, the rate of most accelerated nonconvex stochastic optimization algorithms that adopt additional techniques, such as Nesterov’s momentum acceleration, negative curvature search, as well as quadratic and cubic regularization tricks. Our novel analysis gives new insights into nonconvex SGD and can be potentially generalized to a broad class of stochastic optimization algorithms.}
}
@InProceedings{fei19a,
title = {Achieving the Bayes Error Rate in Stochastic Block Model by SDP, Robustly},
author = {Fei, Yingjie and Chen, Yudong},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1235--1269},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/fei19a/fei19a.pdf},
url = {http://proceedings.mlr.press/v99/fei19a.html},
abstract = {We study the statistical performance of the semidefinite programming (SDP) relaxation approach for clustering under the binary symmetric Stochastic Block Model (SBM). We show that the SDP achieves an error rate of the form $\exp\left[-(1-o(1))\frac{n I}{2}\right]$, where $I$ is an appropriate information-theoretic measure of the signal-to-noise ratio. This bound matches the minimax lower bound on the optimal Bayes error rate for this problem, and improves upon existing results that are sub-optimal by a multiplicative constant in the exponent. As a corollary, our result implies that SDP achieves the optimal exact recovery threshold with the correct leading constant. We further show that this error rate of SDP is robust; that is, it remains unchanged under the so-called semirandom model where the graph is modified by a monotone adversary, as well as under the setting with heterogeneous edge probabilities. Our proof is based on a novel primal-dual analysis of the SDP.}
}
@InProceedings{feldman19a,
title = {High probability generalization bounds for uniformly stable algorithms with nearly optimal rate},
author = {Feldman, Vitaly and Vondrak, Jan},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1270--1279},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/feldman19a/feldman19a.pdf},
url = {http://proceedings.mlr.press/v99/feldman19a.html},
abstract = {Algorithmic stability is a classical approach to understanding and analysis of the generalization error of learning algorithms. A notable weakness of most stability-based generalization bounds is that they hold only in expectation. Generalization with high probability has been established in a landmark paper of Bousquet and Elisseeff (2001) albeit at the expense of an additional $\sqrt{n}$ factor in the bound. Specifically, their bound on the estimation error of any $\gamma$-uniformly stable learning algorithm on $n$ samples and range in $[0,1]$ is $O(\gamma \sqrt{n \log(1/\delta)} + \sqrt{\log(1/\delta)/n})$ with probability $\geq 1-\delta$. The $\sqrt{n}$ overhead makes the bound vacuous in the common settings where $\gamma \geq 1/\sqrt{n}$. A stronger bound was recently proved by the authors (Feldman and Vondrak, 2018) that reduces the overhead to at most $O(n^{1/4})$. Still, both of these results give optimal generalization bounds only when $\gamma = O(1/n)$. We prove a nearly tight bound of $O(\gamma \log(n)\log(n/\delta) + \sqrt{\log(1/\delta)/n})$ on the estimation error of any $\gamma$-uniformly stable algorithm. It implies that for algorithms that are uniformly stable with $\gamma = O(1/\sqrt{n})$, estimation error is essentially the same as the sampling error. Our result leads to the first high-probability generalization bounds for multi-pass stochastic gradient descent and regularized ERM for stochastic convex problems with nearly optimal rate — resolving open problems in prior work. Our proof technique is new and we introduce several analysis tools that might find additional applications.}
}
@InProceedings{foster19a,
title = {Sum-of-squares meets square loss: Fast rates for agnostic tensor completion},
author = {Foster, Dylan J. and Risteski, Andrej},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1280--1318},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/foster19a/foster19a.pdf},
url = {http://proceedings.mlr.press/v99/foster19a.html},
abstract = {We study tensor completion in the agnostic setting. In the classical tensor completion problem, we receive $n$ entries of an unknown rank-$r$ tensor and wish to exactly complete the remaining entries. In agnostic tensor completion, we make \emph{no assumption} on the rank of the unknown tensor, but attempt to predict unknown entries as well as the best rank-$r$ tensor. For agnostic learning of third-order tensors with the square loss, we give the first polynomial time algorithm that obtains a “fast” (i.e., $O(1/n)$-type) rate improving over the rate obtained by reduction to matrix completion. Our prediction error rate to compete with the best $d\times{}d\times{}d$ tensor of rank-$r$ is $\tilde{O}(r^{2}d^{3/2}/n)$. We also obtain an exact oracle inequality that trades off estimation and approximation error. Our algorithm is based on the degree-six sum-of-squares relaxation of the tensor nuclear norm. The key feature of our analysis is to show that a certain characterization for the subgradient of the tensor nuclear norm can be encoded in the sum-of-squares proof system. This unlocks the standard toolbox for localization of empirical processes under the square loss, and allows us to establish restricted eigenvalue-type guarantees for various tensor regression models, with tensor completion as a special case. The new analysis of the relaxation complements Barak and Moitra (2016), who gave slow rates for agnostic tensor completion, and Potechin and Steurer (2017), who gave exact recovery guarantees for the noiseless setting. Our techniques are user-friendly, and we anticipate that they will find use elsewhere.}
}
@InProceedings{foster19b,
title = {The Complexity of Making the Gradient Small in Stochastic Convex Optimization},
author = {Foster, Dylan J. and Sekhari, Ayush and Shamir, Ohad and Srebro, Nathan and Sridharan, Karthik and Woodworth, Blake},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1319--1345},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/foster19b/foster19b.pdf},
url = {http://proceedings.mlr.press/v99/foster19b.html},
abstract = {We give nearly matching upper and lower bounds on the oracle complexity of finding $\epsilon$-stationary points $(\|\nabla F(x)\|\leq\epsilon$ in stochastic convex optimization. We jointly analyze the oracle complexity in both the local stochastic oracle model and the global oracle (or, statistical learning) model. This allows us to decompose the complexity of finding near-stationary points into optimization complexity and sample complexity, and reveals some surprising differences between the complexity of stochastic optimization versus learning. Notably, we show that in the global oracle/statistical learning model, only logarithmic dependence on smoothness is required to find a near-stationary point, whereas polynomial dependence on smoothness is necessary in the local stochastic oracle model. In other words, the separation in complexity between the two models can be exponential, and the folklore understanding that smoothness is required to find stationary points is only weakly true for statistical learning. Our upper bounds are based on extensions of a recent “recursive regularization” technique proposed by Allen-Zhu (2018). We show how to extend the technique to achieve near-optimal rates, and in particular show how to leverage the extra information available in the global oracle model. Our algorithm for the global model can be implemented efficiently through finite sum methods, and suggests an interesting new computational-statistical tradeoff.}
}
@InProceedings{foster19c,
title = {Statistical Learning with a Nuisance Component},
author = {Foster, Dylan J. and Syrgkanis, Vasilis},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1346--1348},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/foster19c/foster19c.pdf},
url = {http://proceedings.mlr.press/v99/foster19c.html},
abstract = {We provide excess risk guarantees for statistical learning in a setting where the population risk with respect to which we evaluate the target model depends on an unknown model that must be to be estimated from data (a “nuisance model”). We analyze a two-stage sample splitting meta-algorithm that takes as input two arbitrary estimation algorithms: one for the target model and one for the nuisance model. We show that if the population risk satisfies a condition called Neyman orthogonality, the impact of the nuisance estimation error on the excess risk bound achieved by the meta-algorithm is of second order. Our theorem is agnostic to the particular algorithms used for the target and nuisance and only makes an assumption on their individual performance. This enables the use of a plethora of existing results from statistical learning and machine learning literature to give new guarantees for learning with a nuisance component. Moreover, by focusing on excess risk rather than parameter estimation, we can give guarantees under weaker assumptions than in previous works and accommodate the case where the target parameter belongs to a complex nonparametric class. We characterize conditions on the metric entropy such that oracle rates—rates of the same order as if we knew the nuisance model—are achieved. We also analyze the rates achieved by specific estimation algorithms such as variance-penalized empirical risk minimization, neural network estimation and sparse high-dimensional linear model estimation. We highlight the applicability of our results in four settings of central importance in the literature: 1) heterogeneous treatment effect estimation, 2) offline policy optimization, 3) domain adaptation, and 4) learning with missing data.}
}
@InProceedings{garber19a,
title = {On the Regret Minimization of Nonconvex Online Gradient Ascent for Online PCA},
author = {Garber, Dan},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1349--1373},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/garber19a/garber19a.pdf},
url = {http://proceedings.mlr.press/v99/garber19a.html},
abstract = {In this paper we focus on the problem of Online Principal Component Analysis in the regret minimization framework. For this problem, all existing regret minimization algorithms for the fully-adversarial setting are based on a positive semidefinite convex relaxation, and hence require quadratic memory and SVD computation (either thin of full) on each iteration, which amounts to at least quadratic runtime per iteration. This is in stark contrast to a corresponding stochastic i.i.d. variant of the problem, which was studied extensively lately, and admits very efficient gradient ascent algorithms that work directly on the natural non-convex formulation of the problem, and hence require only linear memory and linear runtime per iteration. This raises the question: \textit{can non-convex online gradient ascent algorithms be shown to minimize regret in online adversarial settings?} In this paper we take a step forward towards answering this question. We introduce an \textit{adversarially-perturbed spiked-covariance model} in which, each data point is assumed to follow a fixed stochastic distribution with a non-zero spectral gap in the covariance matrix, but is then perturbed with some adversarial vector. This model is a natural extension of a well studied standard \textit{stochastic} setting that allows for non-stationary (adversarial) patterns to arise in the data and hence, might serve as a significantly better approximation for real-world data-streams. We show that in an interesting regime of parameters, when the non-convex online gradient ascent algorithm is initialized with a “warm-start" vector, it provably minimizes the regret with high probability. We further discuss the possibility of computing such a “warm-start" vector, and also the use of regularization to obtain fast regret rates. Our theoretical findings are supported by empirical experiments on both synthetic and real-world data.}
}
@InProceedings{gasnikov19a,
title = {Optimal Tensor Methods in Smooth Convex and Uniformly ConvexOptimization},
author = {Gasnikov, Alexander and Dvurechensky, Pavel and Gorbunov, Eduard and Vorontsova, Evgeniya and Selikhanovych, Daniil and Uribe, C\'esar A.},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1374--1391},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/gasnikov19a/gasnikov19a.pdf},
url = {http://proceedings.mlr.press/v99/gasnikov19a.html},
abstract = {We consider convex optimization problems with the objective function having Lipshitz-continuous $p$-th order derivative, where $p\geq 1$. We propose a new tensor method, which closes the gap between the lower $\Omega\left(\e^{-\frac{2}{3p+1}} \right)$ and upper $O\left(\e^{-\frac{1}{p+1}} \right)$ iteration complexity bounds for this class of optimization problems. We also consider uniformly convex functions, and show how the proposed method can be accelerated under this additional assumption. Moreover, we introduce a $p$-th order condition number which naturally arises in the complexity analysis of tensor methods under this assumption. Finally, we make a numerical study of the proposed optimal method and show that in practice it is faster than the best known accelerated tensor method. We also compare the performance of tensor methods for $p=2$ and $p=3$ and show that the 3rd-order method is superior to the 2nd-order method in practice. }
}
@InProceedings{gasnikov19b,
title = {Near Optimal Methods for Minimizing Convex Functions with Lipschitz $p$-th Derivatives},
author = {Gasnikov, Alexander and Dvurechensky, Pavel and Gorbunov, Eduard and Vorontsova, Evgeniya and Selikhanovych, Daniil and Uribe, C\'esar A. and Jiang, Bo and Wang, Haoyue and Zhang, Shuzhong and Bubeck, S\'ebastien and Jiang, Qijia and Lee, Yin Tat and Li, Yuanzhi and Sidford, Aaron},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1392--1393},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/gasnikov19b/gasnikov19b.pdf},
url = {http://proceedings.mlr.press/v99/gasnikov19b.html},
abstract = {In this merged paper, we consider the problem of minimizing a convex function with Lipschitz-continuous $p$-th order derivatives. Given an oracle which when queried at a point returns the first $p$-derivatives of the function at that point we provide some methods which compute an $\e$ approximate minimizer in $O\left(\e^{-\frac{2}{3p+1}} \right)$ iterations. These methods match known lower bounds up to polylogarithmic factors for constant $p$.}
}
@InProceedings{ge19a,
title = {Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization},
author = {Ge, Rong and Li, Zhize and Wang, Weiyao and Wang, Xiang},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1394--1448},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/ge19a/ge19a.pdf},
url = {http://proceedings.mlr.press/v99/ge19a.html},
abstract = {Variance reduction techniques like SVRG provide simple and fast algorithms for optimizing a convex finite-sum objective. For nonconvex objectives, these techniques can also find a first-order stationary point (with small gradient). However, in nonconvex optimization it is often crucial to find a second-order stationary point (with small gradient and almost PSD hessian). In this paper, we show that Stabilized SVRG (a simple variant of SVRG) can find an $\epsilon$-second-order stationary point using only $\widetilde{O}(n^{2/3}/\epsilon^2+n/\epsilon^{1.5})$ stochastic gradients. To our best knowledge, this is the first second-order guarantee for a simple variant of SVRG. The running time almost matches the known guarantees for finding $\epsilon$-first-order stationary points.}
}
@InProceedings{goel19a,
title = {Learning Ising Models with Independent Failures},
author = {Goel, Surbhi and Kane, Daniel M. and Klivans, Adam R.},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1449--1469},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/goel19a/goel19a.pdf},
url = {http://proceedings.mlr.press/v99/goel19a.html},
abstract = { We give the first efficient algorithm for learning the structure of an Ising model that tolerates independent failures; that is, each entry of the observed sample is missing with some unknown probability $p$. Our algorithm matches the essentially optimal runtime and sample complexity bounds of recent work for learning Ising models due to Klivans and Meka (2017). We devise a novel unbiased estimator for the gradient of the Interaction Screening Objective (ISO) due to Vuffray et al. (2016) and apply a stochastic multiplicative gradient descent algorithm to minimize this objective. Solutions to this minimization recover the neighborhood information of the underlying Ising model on a node by node basis. }
}
@InProceedings{goel19b,
title = {Learning Neural Networks with Two Nonlinear Layers in Polynomial Time},
author = {Goel, Surbhi and Klivans, Adam R.},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1470--1499},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/goel19b/goel19b.pdf},
url = {http://proceedings.mlr.press/v99/goel19b.html},
abstract = { We give a polynomial-time algorithm for learning neural networks with one layer of sigmoids feeding into any Lipschitz, monotone activation function (e.g., sigmoid or ReLU). The algorithm succeeds with respect to {\em any} distribution on the unit ball in $n$ dimensions (hidden weight vectors in the first layer have unit norm). This is the first efficient algorithm for learning a general class of neural networks with more than one nonlinear layer that makes no restrictions on the VC-dimension of the network. Algorithms for learning relaxations of our model (e.g., allowing larger weight vectors in the first layer) would lead to breakthroughs on notoriously hard problems in Boolean function learning. Thus, our results are “best possible” with respect to current techniques. Our algorithm– {\em Alphatron}– is an iterative update rule that combines isotonic regression with kernel methods. We use this algorithm to give a simple reduction for translating PAC learning algorithms to the more general, real-valued setting of {\em probabilistic concepts}, a model that (unlike PAC learning) requires non-i.i.d. noise-tolerance. This substantially improves many longstanding results for PAC learning Boolean functions. }
}
@InProceedings{gopfert19a,
title = {When can unlabeled data improve the learning rate?},
author = {G{\"o}pfert, Christina and Ben-David, Shai and Bousquet, Olivier and Gelly, Sylvain and Tolstikhin, Ilya and Urner, Ruth},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1500--1518},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/gopfert19a/gopfert19a.pdf},
url = {http://proceedings.mlr.press/v99/gopfert19a.html},
abstract = {In semi-supervised classification, one is given access both to labeled and unlabeled data. As unlabeled data is typically cheaper to acquire than labeled data, this setup becomes advantageous as soon as one can exploit the unlabeled data in order to produce a better classifier than with labeled data alone. However, the conditions under which such an improvement is possible are not fully understood yet. Our analysis focuses on improvements in the \emph{minimax} learning rate in terms of the number of labeled examples (with the number of unlabeled examples being allowed to depend on the number of labeled ones). We argue that for such improvements to be realistic and indisputable, certain specific conditions should be satisfied and previous analyses have failed to meet those conditions. We then demonstrate examples where these conditions can be met, in particular showing rate changes from $1/\sqrt{\ell}$ to $e^{-c\ell}$ and from $1/\sqrt{\ell}$ to $1/\ell$. These results improve our understanding of what is and isn’t possible in semi-supervised learning.}
}
@InProceedings{goyal19a,
title = {Sampling and Optimization on Convex Sets in Riemannian Manifolds of Non-Negative Curvature},
author = {Goyal, Navin and Shetty, Abhishek},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1519--1561},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/goyal19a/goyal19a.pdf},
url = {http://proceedings.mlr.press/v99/goyal19a.html},
abstract = {The Euclidean space notion of convex sets (and functions) generalizes to Riemannian manifolds in a natural sense and is called geodesic convexity. Extensively studied computational problems such as convex optimization and sampling in convex sets also have meaningful counterparts in the manifold setting. Geodesically convex optimization is a well-studied problem with ongoing research and considerable recent interest in machine learning and theoretical computer science. In this paper, we study sampling and convex optimization problems over manifolds of non-negative curvature proving polynomial running time in the dimension and other relevant parameters. Our algorithms assume a warm start. We first present a random walk based sampling algorithm and then combine it with simulated annealing for solving convex optimization problems. To our knowledge, these are the first algorithms in the general setting of positively curved manifolds with provable polynomial guarantees under reasonable assumptions, and the first study of the connection between sampling and optimization in this setting.}
}
@InProceedings{gupta19a,
title = {Better Algorithms for Stochastic Bandits with Adversarial Corruptions},
author = {Gupta, Anupam and Koren, Tomer and Talwar, Kunal},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1562--1578},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/gupta19a/gupta19a.pdf},
url = {http://proceedings.mlr.press/v99/gupta19a.html},
abstract = {We study the stochastic multi-armed bandits problem in the presence of adversarial corruption. We present a new algorithm for this problem whose regret is nearly optimal, substantially improving upon previous work. Our algorithm is agnostic to the level of adversarial contamination and can tolerate a significant amount of corruption with virtually no degradation in performance.}
}
@InProceedings{harvey19a,
title = {Tight analyses for non-smooth stochastic gradient descent},
author = {Harvey, Nicholas J.~A. and Liaw, Christopher and Plan, Yaniv and Randhawa, Sikander},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1579--1613},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/harvey19a/harvey19a.pdf},
url = {http://proceedings.mlr.press/v99/harvey19a.html},
abstract = {Consider the problem of minimizing functions that are Lipschitz and strongly convex, but not necessarily differentiable. We prove that after $T$ steps of stochastic gradient descent, the error of the final iterate is $O(\log(T)/T)$ \emph{with high probability}. We also construct a function from this class for which the error of the final iterate of \emph{deterministic} gradient descent is $\Omega(\log(T)/T)$. This shows that the upper bound is tight and that, in this setting, the last iterate of stochastic gradient descent has the same general error rate (with high probability) as deterministic gradient descent. This resolves both open questions posed by Shamir (2012). An intermediate step of our analysis proves that the suffix averaging method achieves error $O(1/T)$ \emph{with high probability}, which is optimal (for any first-order optimization method). This improves results of Rakhlin et al. (2012) and Hazan and Kale (2014), both of which achieved error $O(1/T)$, but only in expectation, and achieved a high probability error bound of $O(\log \log(T)/T)$, which is suboptimal.}
}
@InProceedings{hazla19a,
title = {Reasoning in {B}ayesian Opinion Exchange Networks Is {$\mathsf{PSPACE}$}-Hard},
author = {H\k{a}z\l{}a, Jan and Jadbabaie, Ali and Mossel, Elchanan and Rahimian, M.~Amin},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1614--1648},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/hazla19a/hazla19a.pdf},
url = {http://proceedings.mlr.press/v99/hazla19a.html},
abstract = { We study the Bayesian model of opinion exchange of fully rational agents arranged on a network. In this model, the agents receive private signals that are indicative of an unknown state of the world. Then, they repeatedly announce the state of the world they consider most likely to their neighbors, at the same time updating their beliefs based on their neighbors’ announcements. This model is extensively studied in economics since the work of Aumann (1976) and Geanakoplos and Polemarchakis (1982). It is known that the agents eventually agree with high probability on any network. It is often argued that the computations needed by agents in this model are difficult, but prior to our results there was no rigorous work showing this hardness. We show that it is $\mathsf{PSPACE}$-hard for the agents to compute their actions in this model. Furthermore, we show that it is equally difficult even to approximate an agent’s posterior: It is $\mathsf{PSPACE}$-hard to distinguish between the posterior being almost entirely concentrated on one state of the world or another. }
}
@InProceedings{hopkins19a,
title = {How Hard is Robust Mean Estimation?},
author = {Hopkins, Samuel B. and Li, Jerry},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1649--1682},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/hopkins19a/hopkins19a.pdf},
url = {http://proceedings.mlr.press/v99/hopkins19a.html},
abstract = {Robust mean estimation is the problem of estimating the mean $\mu \in \mathbb{R}^d$ of a $d$-dimensional distribution $D$ from a list of independent samples, an $\varepsilon$-fraction of which have been arbitrarily corrupted by a malicious adversary. Recent algorithmic progress has resulted in the first polynomial-time algorithms which achieve \emph{dimension-independent} rates of error: for instance, if $D$ has covariance $I$, in polynomial-time one may find $\hat{\mu}$ with $\|\mu - \hat{\mu}\| \leq O(\sqrt{\varepsilon})$. However, error rates achieved by current polynomial-time algorithms, while dimension-independent, are sub-optimal in many natural settings, such as when $D$ is sub-Gaussian, or has bounded $4$-th moments. In this work we give worst-case complexity-theoretic evidence that improving on the error rates of current polynomial-time algorithms for robust mean estimation may be computationally intractable in natural settings. We show that several natural approaches to improving error rates of current polynomial-time robust mean estimation algorithms would imply efficient algorithms for the small-set expansion problem, refuting Raghavendra and Steurer’s small-set expansion hypothesis (so long as $P \neq NP$). We also give the first direct reduction to the robust mean estimation problem, starting from a plausible but nonstandard variant of the small-set expansion problem.}
}
@InProceedings{hopkins19b,
title = {A Robust Spectral Algorithm for Overcomplete Tensor Decomposition},
author = {Hopkins, Samuel B. and Schramm, Tselil and Shi, Jonathan},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1683--1722},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/hopkins19b/hopkins19b.pdf},
url = {http://proceedings.mlr.press/v99/hopkins19b.html},
abstract = {We give a spectral algorithm for decomposing overcomplete order-4 tensors, so long as their components satisfy an algebraic non-degeneracy condition that holds for nearly all (all but an algebraic set of measure $0$) tensors over $(\mathbb{R}^d)^{\otimes 4}$ with rank $n \le d^2$. Our algorithm is robust to adversarial perturbations of bounded spectral norm. Our algorithm is inspired by one which uses the sum-of-squares semidefinite programming hierarchy (Ma, Shi, and Steurer STOC’16), and we achieve comparable robustness and overcompleteness guarantees under similar algebraic assumptions. However, our algorithm avoids semidefinite programming and may be implemented as a series of basic linear-algebraic operations. We consequently obtain a much faster running time than semidefinite programming methods: our algorithm runs in time $\tilde O(n^2d^3) \le \tilde O(d^7)$, which is subquadratic in the input size $d^4$ (where we have suppressed factors related to the condition number of the input tensor).}
}
@InProceedings{indyk19a,
title = {Sample-Optimal Low-Rank Approximation of Distance Matrices},
author = {Indyk, Pitor and Vakilian, Ali and Wagner, Tal and Woodruff, David P},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1723--1751},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/indyk19a/indyk19a.pdf},
url = {http://proceedings.mlr.press/v99/indyk19a.html},
abstract = {A distance matrix $A \in \mathbb{R}^{n \times m}$ represents all pairwise distances, $A_{i,j} = d(x_i,y_j)$, between two point sets $x_1,\dotsc,x_n$ and $y_1,\dotsc,y_m$ in an arbitrary metric space $(\mathcal{Z},d)$. Such matrices arise in various computational contexts such as learning image manifolds, handwriting recognition, and multi-dimensional unfolding. In this work we study algorithms for low-rank approximation of distance matrices. Recent work by Bakshi and Woodruff (NeurIPS 2018) showed it is possible to compute a rank-$k$ approximation of a distance matrix in time $O((n+m)^{1+\gamma}) \mathrm{poly}(k,1/\epsilon)$, where $\epsilon>0$ is an error parameter and $\gamma>0$ is an arbitrarily small constant. Notably, their bound is sublinear in the matrix size, which is unachieveable for general matrices. We present an algorithm that is both simpler and more efficient. It reads only $O((n+m)k/\epsilon)$ entries of the input matrix, and has a running time of $O(n+m) \cdot \mathrm{poly}(k,1/\epsilon)$. We complement the sample complexity of our algorithm with a matching lower bound on the number of entries that must be ready by any algorithm. We provide experimental results to validate the approximation quality and running time of our algorithm}
}
@InProceedings{jain19a,
title = {Making the Last Iterate of SGD Information Theoretically Optimal},
author = {Jain, Prateek and Nagaraj, Dheeraj and Netrapalli, Praneeth},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1752--1755},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/jain19a/jain19a.pdf},
url = {http://proceedings.mlr.press/v99/jain19a.html},
abstract = {Stochastic gradient descent (SGD) is one of the most widely used algorithms for large scale optimization problems. While classical theoretical analysis of SGD for convex problems studies (suffix) \emph{averages} of iterates and obtains information theoretically optimal bounds on suboptimality, the \emph{last point} of SGD is, by far, the most preferred choice in practice. The best known results for last point of SGD (Shamir and Zhang, 2013) however, are suboptimal compared to information theoretic lower bounds by a $\log T$ factor, where $T$ is the number of iterations. Harvey et. al (2018) shows that in fact, this additional $\log T$ factor is tight for standard step size sequences of $\OTheta{\frac{1}{\sqrt{t}}}$ and $\OTheta{\frac{1}{t}}$ for non-strongly convex and strongly convex settings, respectively. Similarly, even for subgradient descent (GD) when applied to non-smooth, convex functions, the best known step-size sequences still lead to $O(\log T)$-suboptimal convergence rates (on the final iterate). The main contribution of this work is to design new step size sequences that enjoy information theoretically optimal bounds on the suboptimality of \emph{last point} of SGD as well as GD. We achieve this by designing a modification scheme, that converts one sequence of step sizes to another so that the last point of SGD/GD with modified sequence has the same suboptimality guarantees as the average of SGD/GD with original sequence. We also show that our result holds with high-probability. We validate our results through simulations which demonstrate that the new step size sequence indeed improves the final iterate significantly compared to the standard step size sequences.}
}
@InProceedings{jain19b,
title = {Accuracy-Memory Tradeoffs and Phase Transitions in Belief Propagation},
author = {Jain, Vishesh and Koehler, Frederic and Liu, Jingbo and Mossel, Elchanan},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1756--1771},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/jain19b/jain19b.pdf},
url = {http://proceedings.mlr.press/v99/jain19b.html},
abstract = {The analysis of Belief Propagation and other algorithms for the {\em reconstruction problem} plays a key role in the analysis of community detection in inference on graphs, phylogenetic reconstruction in bioinformatics, and the cavity method in statistical physics. We prove a conjecture of Evans, Kenyon, Peres, and Schulman (2000) which states that any bounded memory message passing algorithm is statistically much weaker than Belief Propagation for the reconstruction problem. More formally, any recursive algorithm with bounded memory for the reconstruction problem on the trees with the binary symmetric channel has a phase transition strictly below the Belief Propagation threshold, also known as the Kesten-Stigum bound. The proof combines in novel fashion tools from recursive reconstruction, information theory, and optimal transport, and also establishes an asymptotic normality result for BP and other message-passing algorithms near the critical threshold.}
}
@InProceedings{ji19a,
title = {The implicit bias of gradient descent on nonseparable data},
author = {Ji, Ziwei and Telgarsky, Matus},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1772--1798},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/ji19a/ji19a.pdf},
url = {http://proceedings.mlr.press/v99/ji19a.html},
abstract = {Gradient descent, when applied to the task of logistic regression, outputs iterates which are biased to follow a unique ray defined by the data. The direction of this ray is the maximum margin predictor of a maximal linearly separable subset of the data; the gradient descent iterates converge to this ray in direction at the rate $\cO(\nicefrac{\ln\ln t }{\ln t})$. The ray does not pass through the origin in general, and its offset is the bounded global optimum of the risk over the remaining data; gradient descent recovers this offset at a rate $\cO(\nicefrac{(\ln t)^2}{\sqrt{t}})$.}
}
@InProceedings{jiang19a,
title = {An Optimal High-Order Tensor Method for Convex Optimization},
author = {Jiang, Bo and Wang, Haoyue and Zhang, Shuzhong},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1799--1801},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/jiang19a/jiang19a.pdf},
url = {http://proceedings.mlr.press/v99/jiang19a.html},
abstract = {This paper is concerned with finding an optimal algorithm for minimizing a composite convex objective function. The basic setting is that the objective is the sum of two convex functions: the first function is smooth with up to the d-th order derivative information available, and the second function is possibly non-smooth, but its proximal tensor mappings can be computed approximately in an efficient manner. The problem is to find – in that setting – the best possible (optimal) iteration complexity for convex optimization. Along that line, for the smooth case (without the second non-smooth part in the objective), Nesterov (1983) proposed an optimal algorithm for the first-order methods (d=1) with iteration complexity O( 1 / k^2 ). A high-order tensor algorithm with iteration complexity of O( 1 / k^{d+1} ) was proposed by Baes (2009) and Nesterov (2018). In this paper, we propose a new high-order tensor algorithm for the general composite case, with the iteration complexity of O( 1 / k^{(3d+1)/2} ), which matches the lower bound for the d-th order methods as established in Nesterov (2018) and Shamir et al. (2018), and hence is optimal. Our approach is based on the Accelerated Hybrid Proximal Extragradient (A-HPE) framework proposed in Monteiro and Svaiter (2013), where a bisection procedure is installed for each A-HPE iteration. At each bisection step a proximal tensor subproblem is approximately solved, and the total number of bisection steps per A-HPE iteration is bounded by a logarithmic factor in the precision required.}
}
@InProceedings{jun19a,
title = {Parameter-Free Online Convex Optimization with Sub-Exponential Noise},
author = {Jun, Kwang-Sung and Orabona, Francesco},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1802--1823},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/jun19a/jun19a.pdf},
url = {http://proceedings.mlr.press/v99/jun19a.html},
abstract = { We consider the problem of unconstrained online convex optimization (OCO) with sub-exponential noise, a strictly more general problem than the standard OCO. In this setting, the learner receives a subgradient of the loss functions corrupted by sub-exponential noise and strives to achieve optimal regret guarantee, without knowledge of the competitor norm, i.e., in a parameter-free way. Recently, Cutkosky and Boahen (COLT 2017) proved that, given unbounded subgradients, it is impossible to guarantee a sublinear regret due to an exponential penalty. This paper shows that it is possible to go around the lower bound by allowing the observed subgradients to be unbounded via stochastic noise. However, the presence of unbounded noise in unconstrained OCO is challenging; existing algorithms do not provide near-optimal regret bounds or fail to have a guarantee. So, we design a novel parameter-free OCO algorithm for Banach space, which we call BANCO, via a reduction to betting on noisy coins. We show that BANCO achieves the optimal regret rate in our problem. Finally, we show the application of our results to obtain a parameter-free locally private stochastic subgradient descent algorithm, and the connection to the law of iterated logarithms. }
}
@InProceedings{juneja19a,
title = {Sample complexity of partition identification using multi-armed bandits},
author = {Juneja, Sandeep and Krishnasamy, Subhashini},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1824--1852},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/juneja19a/juneja19a.pdf},
url = {http://proceedings.mlr.press/v99/juneja19a.html},
abstract = {Given a vector of probability distributions, or arms, each of which can be sampled independently, we consider the problem of identifying the partition to which this vector belongs from a finitely partitioned universe of such vector of distributions. We study this as a pure exploration problem in multi-armed bandit settings and develop sample complexity bounds on the total mean number of samples required for identifying the correct partition with high probability. This framework subsumes well studied problems such as finding the best arm or the best few arms. We consider distributions belonging to the single parameter exponential family and primarily consider partitions where the vector of means of arms lie either in a given set or its complement. The sets considered correspond to distributions where there exists a mean above a specified threshold, where the set is a half space and where either the set or its complement is a polytope, or more generally, a convex set. In these settings, we characterize the lower bounds on mean number of samples for each arm highlighting their dependence on the problem geometry. Further, inspired by the lower bounds, we propose algorithms that can match these bounds asymptotically with decreasing probability of error. Applications of this framework may be diverse. We briefly discuss a few associated with simulation in finance.}
}
@InProceedings{kamath19a,
title = {Privately Learning High-Dimensional Distributions},
author = {Kamath, Gautam and Li, Jerry and Singhal, Vikrant and Ullman, Jonathan},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1853--1902},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/kamath19a/kamath19a.pdf},
url = {http://proceedings.mlr.press/v99/kamath19a.html},
abstract = {We present novel, computationally efficient, and differentially private algorithms for two fundamental high-dimensional learning problems: learning a multivariate Gaussian and learning a product distribution over the Boolean hypercube in total variation distance. The sample complexity of our algorithms nearly matches the sample complexity of the optimal non-private learners for these tasks in a wide range of parameters, showing that privacy comes essentially for free for these problems. In particular, in contrast to previous approaches, our algorithm for learning Gaussians does not require strong a priori bounds on the range of the parameters. Our algorithms introduce a novel technical approach to reducing the sensitivity of the estimation procedure that we call recursive private preconditioning.}
}
@InProceedings{kane19a,
title = {On Communication Complexity of Classification Problems},
author = {Kane, Daniel and Livni, Roi and Moran, Shay and Yehudayoff, Amir},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1903--1943},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/kane19a/kane19a.pdf},
url = {http://proceedings.mlr.press/v99/kane19a.html},
abstract = {This work studies distributed learning in the spirit of Yao’s model of communication complexity: consider a two-party setting, where each of the players gets a list of labelled examples and they communicate in order to jointly perform some learning task. To naturally fit into the framework of learning theory, the players can send each other examples (as well as bits) where each example/bit costs one unit of communication. This enables a uniform treatment of infinite classes such as half-spaces in $\R^d$, which are ubiquitous in machine learning. We study several fundamental questions in this model. For example, we provide combinatorial characterizations of the classes that can be learned with efficient communication in the proper-case as well as in the improper-case. These findings imply unconditional separations in this context between various learning tasks, e.g. realizable versus agnostic learning, proper versus improper learning, etcetera. %They also imply lower bounds that match the performance %of algorithm from previous works. The derivation of these results hinges on a type of decision problems we term “{\it realizability problems}” where the goal is deciding whether a distributed input sample is consistent with an hypothesis from a pre-specified class. From a technical perspective, the protocols we devise (i.e. the upper bounds) are based on ideas from machine learning and the impossibility results (i.e. the lower bounds) are based on ideas from communication complexity.}
}
@InProceedings{karimi19a,
title = {Non-asymptotic Analysis of Biased Stochastic Approximation Scheme},
author = {Karimi, Belhal and Miasojedow, Blazej and Moulines, Eric and Wai, Hoi-To},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1944--1974},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/karimi19a/karimi19a.pdf},
url = {http://proceedings.mlr.press/v99/karimi19a.html},
abstract = {Stochastic approximation (SA) is a key method used in statistical learning. Recently, its non-asymptotic convergence analysis has been considered in many papers. However, most of the prior analyses are made under restrictive assumptions such as unbiased gradient estimates and convex objective function, which significantly limit their applications to sophisticated tasks such as online and reinforcement learning. These restrictions are all essentially relaxed in this work. In particular, we analyze a general SA scheme to minimize a non-convex, smooth objective function. We consider update procedure whose drift term depends on a state-dependent Markov chain and the mean field is not necessarily of gradient type, covering approximate second-order method and allowing asymptotic bias for the one-step updates. We illustrate these settings with the online EM algorithm and the policy-gradient method for average reward maximization in reinforcement learning.}
}
@InProceedings{karnin19a,
title = {Discrepancy, Coresets, and Sketches in Machine Learning},
author = {Karnin, Zohar and Liberty, Edo},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1975--1993},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/karnin19a/karnin19a.pdf},
url = {http://proceedings.mlr.press/v99/karnin19a.html},
abstract = {This paper defines the notion of class discrepancy for families of functions. It shows that low discrepancy classes admit small offline and streaming coresets. We provide general techniques for bounding the class discrepancy of machine learning problems. As corollaries of the general technique we bound the discrepancy of logistic regression, sigmoid activation loss, matrix covariance, kernel density and any analytic function of the dot product or the squared distance. Our result resolves a long-standing open problem regarding the coreset complexity of Gaussian kernel density estimation. We provide two more related but independent results. First, an exponential improvement of the widely used merge-and-reduce trick which gives improved streaming sketches for any low discrepancy problem. Second, an extremely simple deterministic algorithm for finding low discrepancy sequences (and therefore coresets) for any positive semi-definite kernel. This paper establishes some explicit connections between class discrepancy, coreset complexity, learnability, and streaming algorithms.}
}
@InProceedings{kotlowski19a,
title = {Bandit Principal Component Analysis},
author = {Kot{\l}owski, Wojciech and Neu, Gergely},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {1994--2024},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/kotlowski19a/kotlowski19a.pdf},
url = {http://proceedings.mlr.press/v99/kotlowski19a.html},
abstract = {We consider a partial-feedback variant of the well-studied online PCA problem where a learner attempts to predict a sequence of $d$-dimensional vectors in terms of a quadratic loss, while only having limited feedback about the environment’s choices. We focus on a natural notion of bandit feedback where the learner only observes the loss associated with its own prediction. Based on the classical observation that this decision-making problem can be lifted to the space of density matrices, we propose an algorithm that is shown to achieve a regret of $O(d^{3/2}\sqrt{T})$ after $T$ rounds in the worst case. We also prove data-dependent bounds that improve on the basic result when the loss matrices of the environment have bounded rank or the loss of the best action is bounded. One version of our algorithm runs in $O(d)$ time per trial which massively improves over every previously known online PCA method. We complement these results by a lower bound of $\Omega(d\sqrt{T})$.}
}
@InProceedings{krishnamurthy19a,
title = {Contextual bandits with continuous actions: Smoothing, zooming, and adapting},
author = {Krishnamurthy, Akshay and Langford, John and Slivkins, Aleksandrs and Zhang, Chicheng},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {2025--2027},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/krishnamurthy19a/krishnamurthy19a.pdf},
url = {http://proceedings.mlr.press/v99/krishnamurthy19a.html},
abstract = {We study contextual bandit learning for any competitor policy class and continuous action space. We obtain two qualitatively different regret bounds: one competes with a smoothed version of the policy class under no continuity assumptions, while the other requires standard Lipschitz assumptions. Both bounds exhibit data-dependent “zooming" behavior and, with no tuning, yield improved guarantees for benign problems. We also study adapting to unknown smoothness parameters, establishing a price-of-adaptivity and deriving optimal adaptive algorithms that require no additional information.}
}
@InProceedings{kuzborskij19a,
title = {Distribution-Dependent Analysis of Gibbs-ERM Principle},
author = {Kuzborskij, Ilja and Cesa-Bianchi, Nicol\`{o} and Szepesv\'ari, Csaba},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {2028--2054},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/kuzborskij19a/kuzborskij19a.pdf},
url = {http://proceedings.mlr.press/v99/kuzborskij19a.html},
abstract = {Gibbs-ERM learning is a natural idealized model of learning with stochastic optimization algorithms (such as SGLD and —to some extent— SGD), while it also arises in other contexts, including PAC-Bayesian theory, and sampling mechanisms. In this work we study the excess risk suffered by a Gibbs-ERM learner that uses non-convex, regularized empirical risk with the goal to understand the interplay between the data-generating distribution and learning in large hypothesis spaces. Our main results are \emph{distribution-dependent} upper bounds on several notions of excess risk. We show that, in all cases, the distribution-dependent excess risk is essentially controlled by the \emph{effective dimension} $\text{tr}\left(\boldsymbol{H}^{\star} (\boldsymbol{H}^{\star} + \lambda \boldsymbol{I})^{-1}\right)$ of the problem, where $\boldsymbol{H}^{\star}$ is the Hessian matrix of the risk at a local minimum. This is a well-established notion of effective dimension appearing in several previous works, including the analyses of SGD and ridge regression, but ours is the first work that brings this dimension to the analysis of learning using Gibbs densities. The distribution-dependent view we advocate here improves upon earlier results of Raginsky et al. 2017, and can yield much tighter bounds depending on the interplay between the data-generating distribution and the loss function. The first part of our analysis focuses on the \emph{localized} excess risk in the vicinity of a fixed local minimizer. This result is then extended to bounds on the \emph{global} excess risk, by characterizing probabilities of local minima (and their complement) under Gibbs densities, a results which might be of independent interest.}
}
@InProceedings{kwon19a,
title = {Global Convergence of the EM Algorithm for Mixtures of Two Component Linear Regression},
author = {Kwon, Jeongyeol and Qian, Wei and Caramanis, Constantine and Chen, Yudong and Davis, Damek},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {2055--2110},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/kwon19a/kwon19a.pdf},
url = {http://proceedings.mlr.press/v99/kwon19a.html},
abstract = {The Expectation-Maximization algorithm is perhaps the most broadly used algorithm for inference of latent variable problems. A theoretical understanding of its performance, however, largely remains lacking. Recent results established that EM enjoys global convergence for Gaussian Mixture Models. For Mixed Linear Regression, however, only local convergence results have been established, and those only for the high SNR regime. We show here that EM converges for mixed linear regression with two components (it is known that it may fail to converge for three or more), and moreover that this convergence holds for random initialization. Our analysis reveals that EM exhibits very different behavior in Mixed Linear Regression from its behavior in Gaussian Mixture Models, and hence our proofs require the development of several new ideas.}
}
@InProceedings{lattimore19a,
title = {An Information-Theoretic Approach to Minimax Regret in Partial Monitoring},
author = {Lattimore, Tor and Szepesv{\'a}ri, Csaba},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {2111--2139},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/lattimore19a/lattimore19a.pdf},
url = {http://proceedings.mlr.press/v99/lattimore19a.html},
abstract = { We prove a new minimax theorem connecting the worst-case Bayesian regret and minimax regret under finite-action partial monitoring with no assumptions on the space of signals or decisions of the adversary. We then generalise the information-theoretic tools of Russo and Van Roy (2016) for proving Bayesian regret bounds and combine them with the minimax theorem to derive minimax regret bounds for various partial monitoring settings. The highlight is a clean analysis of ‘easy’ and ‘hard’ finite partial monitoring, with new regret bounds that are independent of arbitrarily large game-dependent constants and eliminate the logarithmic dependence on the horizon for easy games that appeared in earlier work. The power of the generalised machinery is further demonstrated by proving that the minimax regret for $k$-armed adversarial bandits is at most $\sqrt{2kn}$, improving on existing results by a factor of 2. Finally, we provide a simple analysis of the cops and robbers game, also improving best known constants. }
}
@InProceedings{lee19a,
title = {Solving Empirical Risk Minimization in the Current Matrix Multiplication Time},
author = {Lee, Yin Tat and Song, Zhao and Zhang, Qiuyi},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {2140--2157},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/lee19a/lee19a.pdf},
url = {http://proceedings.mlr.press/v99/lee19a.html},
abstract = {Many convex problems in machine learning and computer science share the same form: \begin{align*} \min_{x} \sum_{i} f_i( A_i x + b_i), \end{align*} where $f_i$ are convex functions on $\R^{n_i}$ with constant $n_i$, $A_i \in \R^{n_i \times d}$, $b_i \in \R^{n_i}$ and $\sum_i n_i = n$. This problem generalizes linear programming and includes many problems in empirical risk minimization. In this paper, we give an algorithm that runs in time \begin{align*} O^* ( ( n^{\omega} + n^{2.5 - \alpha/2} + n^{2+ 1/6} ) \log (n / \delta) ) \end{align*} where $\omega$ is the exponent of matrix multiplication, $\alpha$ is the dual exponent of matrix multiplication, and $\delta$ is the relative accuracy. Note that the runtime has only a log dependence on the condition numbers or other data dependent parameters and these are captured in $\delta$. For the current bound $\omega \sim 2.38$ [Vassilevska Williams’12, Le Gall’14] and $\alpha \sim 0.31$ [Le Gall, Urrutia’18], our runtime $O^* ( n^{\omega} \log (n / \delta))$ matches the current best for solving a dense least squares regression problem, a special case of the problem we consider. Very recently, [Alman’18] proved that all the current known techniques can not give a better $\omega$ below $2.168$ which is larger than our $2+1/6$. Our result generalizes the very recent result of solving linear programs in the current matrix multiplication time [Cohen, Lee, Song’19] to a more broad class of problems. Our algorithm proposes two concepts which are different from [Cohen, Lee, Song’19] :\ $\bullet$ We give a robust deterministic central path method, whereas the previous one is a stochastic central path which updates weights by a random sparse vector. \ $\bullet$ We propose an efficient data-structure to maintain the central path of interior point methods even when the weights update vector is dense. }
}
@InProceedings{li19a,
title = {On Mean Estimation for General Norms with Statistical Queries},
author = {Li, Jerry and Nikolov, Aleksandar and Razenshteyn, Ilya and Waingarten, Erik},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {2158--2172},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/li19a/li19a.pdf},
url = {http://proceedings.mlr.press/v99/li19a.html},
abstract = {We study the problem of mean estimation for high-dimensional distributions given access to a statistical query oracle. For a normed space $X = (\mathbb{R}^d, \|\cdot\|_X)$ and a distribution supported on vectors $x \in \mathbb{R}^d$ with $\|x\|_{X} \leq 1$, the task is to output an estimate $\hat{\mu} \in \mathbb{R}^d$ which is $\varepsilon$-close in the distance induced by $\|\cdot\|_X$ to the true mean of the distribution. We obtain sharp upper and lower bounds for the statistical query complexity of this problem when the the underlying norm is \emph{symmetric} as well as for Schatten-$p$ norms, answering two questions raised by Feldman, Guzmán, and Vempala (SODA 2017).}
}
@InProceedings{li19b,
title = {Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits},
author = {Li, Yingkai and Wang, Yining and Zhou, Yuan},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {2173--2174},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/li19b/li19b.pdf},
url = {http://proceedings.mlr.press/v99/li19b.html},
abstract = {We study the linear contextual bandit problem with finite action sets. When the problem dimension is $d$, the time horizon is $T$, and there are $n \leq 2^{d/2}$ candidate actions per time period, we (1) show that the minimax expected regret is $\Omega(\sqrt{dT \log T \log n})$ for every algorithm, and (2) introduce a Variable-Confidence-Level (VCL) SupLinUCB algorithm whose regret matches the lower bound up to iterated logarithmic factors. Our algorithmic result saves two $\sqrt{\log T}$ factors from previous analysis, and our information-theoretical lower bound also improves previous results by one $\sqrt{\log T}$ factor, revealing a regret scaling quite different from classical multi-armed bandits in which no logarithmic $T$ term is present in minimax regret. Our proof techniques include variable confidence levels and a careful analysis of layer sizes of SupLinUCB on the upper bound side, and delicately constructed adversarial sequences showing the tightness of elliptical potential lemmas on the lower bound side. }
}
@InProceedings{liu19a,
title = {Sharp Theoretical Analysis for Nonparametric Testing under Random Projection},
author = {Liu, Meimei and Shang, Zuofeng and Cheng, Guang},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {2175--2209},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/liu19a/liu19a.pdf},
url = {http://proceedings.mlr.press/v99/liu19a.html},
abstract = {A common challenge in nonparametric inference is its high computational complexity when data volume is large. In this paper, we develop computationally efficient nonparametric testing by employing a random projection strategy. In the specific kernel ridge regression setup, a simple distance-based test statistic is proposed. Notably, we derive the minimum number of random projections that is sufficient for achieving testing optimality in terms of the minimax rate. As a by-product, the lower bound of projection dimension for minimax optimal estimation derived in Yang (2017) is proven to be sharp. One technical contribution is to establish upper bounds for a range of tail sums of empirical kernel eigenvalues. }
}
@InProceedings{madan19a,
title = {Combinatorial Algorithms for Optimal Design},
author = {Madan, Vivek and Singh, Mohit and Tantipongpipat, Uthaipon and Xie, Weijun},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {2210--2258},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/madan19a/madan19a.pdf},
url = {http://proceedings.mlr.press/v99/madan19a.html},
abstract = {In an optimal design problem, we are given a set of linear experiments $v_1,…,v_n\in \mathbb{R}^d$ and $k \geq d$, and our goal is to select a set or a multiset $S \subseteq [n]$ of size $k$ such that $\Phi((\sum_{i \in S} v_i v_i^\top )^{-1})$ is minimized. When $\Phi(M) = Determinant(M)^{1/d}$, the problem is known as the D-optimal design problem, and when $\Phi(M) = Trace(M)$, it is known as the A-optimal design problem. One of the most common heuristics used in practice to solve these problems is the local search heuristic, also known as the Fedorov’s exchange method (Fedorov, 1972). This is due to its simplicity and its empirical performance (Cook and Nachtrheim, 1980; Miller and Nguyen, 1994; Atkinson et al., 2007). However, despite its wide usage no theoretical bound has been proven for this algorithm. In this paper, we bridge this gap and prove approximation guarantees for the local search algorithms for D-optimal design and A-optimal design problems. We show that the local search algorithms are asymptotically optimal when $\frac{k}{d}$ is large. In addition to this, we also prove similar approximation guarantees for the greedy algorithms for D-optimal design and A-optimal design problems when $\frac{k}{d}$ is large.}
}
@InProceedings{mangoubi19a,
title = {Nonconvex sampling with the Metropolis-adjusted Langevin algorithm},
author = {Mangoubi, Oren and Vishnoi, Nisheeth K},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {2259--2293},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/mangoubi19a/mangoubi19a.pdf},
url = {http://proceedings.mlr.press/v99/mangoubi19a.html},
abstract = {The Langevin Markov chain algorithms are widely deployed methods to sample from distributions in challenging high-dimensional and non-convex statistics and machine learning applications. Despite this, current bounds for the Langevin algorithms are worse than those of competing algorithms in many important situations, for instance when sampling from weakly log-concave distributions, or when sampling or optimizing non-convex log-densities. We obtain improved bounds in many of these situations, showing that the Metropolis-adjusted Langevin algorithm (MALA) is faster than the best bounds for its competitor algorithms when the target distribution satisfies weak third- and fourth- order regularity properties associated with the input data. In many settings, our regularity conditions are weaker than the usual Euclidean operator norm regularity properties, allowing us to show faster bounds for a much larger class of distributions than would be possible with the usual Euclidean operator norm approach, including in statistics and machine learning applications where the data satisfy a certain incoherence condition. In particular, we show that using our regularity conditions one can obtain faster bounds for applications which include sampling problems in Bayesian logistic regression with weakly convex priors, and the nonconvex optimization problem of learning linear classifiers with zero-one loss functions. Our main technical contribution is an analysis of the Metropolis acceptance probability of MALA in terms of its “energy-conservation error," and a bound for this error in terms of third- and fourth- order regularity conditions. The combination of this higher-order analysis of the energy conservation error with the conductance method is key to obtaining bounds which have a sub-linear dependence on the dimension $d$ in the non-strongly logconcave setting.}
}
@InProceedings{marteau-ferey19a,
title = {Beyond Least-Squares: Fast Rates for Regularized Empirical Risk Minimization through Self-Concordance},
author = {Marteau{-}Ferey, Ulysse and Ostrovskii, Dmitrii and Bach, Francis and Rudi, Alessandro},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {2294--2340},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/marteau-ferey19a/marteau-ferey19a.pdf},
url = {http://proceedings.mlr.press/v99/marteau-ferey19a.html},
abstract = {We consider learning methods based on the regularization of a convex empirical risk by a squared Hilbertian norm, a setting that includes linear predictors and non-linear predictors through positive-definite kernels. In order to go beyond the generic analysis leading to convergence rates of the excess risk as $O(1/\sqrt{n})$ from $n$ observations, we assume that the individual losses are self-concordant, that is, their third-order derivatives are bounded by their second-order derivatives. This setting includes least-squares, as well as all generalized linear models such as logistic and softmax regression. For this class of losses, we provide a bias-variance decomposition and show that the assumptions commonly made in least-squares regression, such as the source and capacity conditions, can be adapted to obtain fast non-asymptotic rates of convergence by improving the bias terms, the variance terms or both.}
}
@InProceedings{massoulie19a,
title = {Planting trees in graphs, and finding them back},
author = {Massouli\'{e}, Laurent and Stephan, Ludovic and Towsley, Don},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {2341--2371},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/massoulie19a/massoulie19a.pdf},
url = {http://proceedings.mlr.press/v99/massoulie19a.html},
abstract = {In this paper we study the two inference problems of detection and reconstruction in the context of planted structures in sparse Erdős-Rényi random graphs $\mathcal G(n,\lambda/n)$ with fixed average degree $\lambda>0$. Motivated by a problem of communication security, we focus on the case where the planted structure consists in the addition of a tree graph. In the case of planted line graphs, we establish the following phase diagram for detection and reconstruction. In a low density region where the average degree $\lambda$ of the original graph is below some critical value $\lambda_c=1$, both detection and reconstruction go from impossible to easy as the line length $K$ crosses some critical value $K^*=\ln(n)/\ln(1/\lambda)$, where $n$ is the number of nodes in the graph. In a high density region where $\lambda>\lambda_c$, detection goes from impossible to easy as $K$ goes from $o(\sqrt{n})$ to $\omega(\sqrt{n})$. In contrast, reconstruction remains impossible so long as $K=o(n)$. We then consider planted $D$-ary trees of varying depth $h$ and $2\le D\le O(1)$. For these we identify a low-density region $\lambda<\lambda_D$, where $\lambda_D$ is the threshold for emergence of the $D$-core in Erdős-Rényi random graphs $\mathcal G(n,\lambda/n)$ for which the following holds. There is a threshold $h*=g(D)\ln(\ln(n))$ with the following properties. Detection goes from impossible to feasible as $h$ crosses $h*$. Interestingly, we show that only partial reconstruction is feasible at best for $h\ge h*$. We conjecture a similar picture to hold for $D$-ary trees as for lines in the high-density region $\lambda>\lambda_D$, but confirm only the following part of this picture: Detection is easy for $D$-ary trees of size $\omega(\sqrt{n})$, while at best only partial reconstruction is feasible for $D$-ary trees of any size $o(n)$. These results provide a clear contrast with the corresponding picture for detection and reconstruction of {\em low rank} planted structures, such as dense subgraphs and block communities. In the examples we study, there is i) an absence of hard phases for both detection and reconstruction, and ii) a discrepancy between detection and reconstruction, the latter being impossible for a wide range of parameters where detection is easy. The latter property does not hold for previously studied low rank planted structures.}
}
@InProceedings{maurer19a,
title = {Uniform concentration and symmetrization for weak interactions},
author = {Maurer, Andreas and Pontil, Massimiliano},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {2372--2387},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/maurer19a/maurer19a.pdf},
url = {http://proceedings.mlr.press/v99/maurer19a.html},
abstract = {The method to derive uniform bounds with Gaussian and Rademacher complexities is extended to the case where the sample average is replaced by a nonlinear statistic. Tight bounds are obtained for U-statistics, smoothened L-statistics and error functionals of l2-regularized algorithms.}
}
@InProceedings{mei19a,
title = {Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit},
author = {Mei, Song and Misiakiewicz, Theodor and Montanari, Andrea},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {2388--2464},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/mei19a/mei19a.pdf},
url = {http://proceedings.mlr.press/v99/mei19a.html},
abstract = {We consider learning two layer neural networks using stochastic gradient descent. The mean-field description of this learning dynamics approximates the evolution of the network weights by an evolution in the space of probability distributions in $\mathbb{R}^D$ (where $D$ is the number of parameters associated to each neuron). This evolution can be defined through a partial differential equation or, equivalently, as the gradient flow in the Wasserstein space of probability distributions. Earlier work shows that (under some regularity assumptions), the mean field description is accurate as soon as the number of hidden units is much larger than the dimension $D$. In this paper we establish stronger and more general approximation guarantees. First of all, we show that the number of hidden units only needs to be larger than a quantity dependent on the regularity properties of the data, and independent of the dimensions. Next, we generalize this analysis to the case of unbounded activation functions, which was not covered by earlier bounds. We extend our results to noisy stochastic gradient descent. Finally, we show that kernel ridge regression can be recovered as a special limit of the mean field analysis. }
}
@InProceedings{merlis19a,
title = {Batch-Size Independent Regret Bounds for the Combinatorial Multi-Armed Bandit Problem},
author = {Merlis, Nadav and Mannor, Shie},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {2465--2489},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/merlis19a/merlis19a.pdf},
url = {http://proceedings.mlr.press/v99/merlis19a.html},
abstract = {We consider the combinatorial multi-armed bandit (CMAB) problem, where the reward function is nonlinear. In this setting, the agent chooses a batch of arms on each round and receives feedback from each arm of the batch. The reward that the agent aims to maximize is a function of the selected arms and their expectations. In many applications, the reward function is highly nonlinear, and the performance of existing algorithms relies on a global Lipschitz constant to encapsulate the function’s nonlinearity. This may lead to loose regret bounds, since by itself, a large gradient does not necessarily cause a large regret, but only in regions where the uncertainty in the reward’s parameters is high. To overcome this problem, we introduce a new smoothness criterion, which we term \emph{Gini-weighted smoothness}, that takes into account both the nonlinearity of the reward and concentration properties of the arms. We show that a linear dependence of the regret in the batch size in existing algorithms can be replaced by this smoothness parameter. This, in turn, leads to much tighter regret bounds when the smoothness parameter is batch-size independent. For example, in the probabilistic maximum coverage (PMC) problem, that has many applications, including influence maximization, diverse recommendations and more, we achieve dramatic improvements in the upper bounds. We also prove matching lower bounds for the PMC problem and show that our algorithm is tight, up to a logarithmic factor in the problem’s parameters.}
}
@InProceedings{mhammedi19a,
title = {Lipschitz Adaptivity with Multiple Learning Rates in Online Learning},
author = {Mhammedi, Zakaria and Koolen, Wouter M and Van Erven, Tim},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {2490--2511},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/mhammedi19a/mhammedi19a.pdf},
url = {http://proceedings.mlr.press/v99/mhammedi19a.html},
abstract = {We aim to design adaptive online learning algorithms that take advantage of any special structure that might be present in the learning task at hand, with as little manual tuning by the user as possible. A fundamental obstacle that comes up in the design of such adaptive algorithms is to calibrate a so-called step-size or learning rate hyperparameter depending on variance, gradient norms, etc. A recent technique promises to overcome this difficulty by maintaining multiple learning rates in parallel. This technique has been applied in the MetaGrad algorithm for online convex optimization and the Squint algorithm for prediction with expert advice. However, in both cases the user still has to provide in advance a Lipschitz hyperparameter that bounds the norm of the gradients. Although this hyperparameter is typically not available in advance, tuning it correctly is crucial: if it is set too small, the methods may fail completely; but if it is taken too large, performance deteriorates significantly. In the present work we remove this Lipschitz hyperparameter by designing new versions of MetaGrad and Squint that adapt to its optimal value automatically. We achieve this by dynamically updating the set of active learning rates. For MetaGrad, we further improve the computational efficiency of handling constraints on the domain of prediction, and we remove the need to specify the number of rounds in advance.}
}
@InProceedings{montasser19a,
title = {VC Classes are Adversarially Robustly Learnable, but Only Improperly},
author = {Montasser, Omar and Hanneke, Steve and Srebro, Nathan},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {2512--2530},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/montasser19a/montasser19a.pdf},
url = {http://proceedings.mlr.press/v99/montasser19a.html},
abstract = {We study the question of learning an adversarially robust predictor. We show that any hypothesis class $\mathcal{H}$ with finite VC dimension is robustly PAC learnable with an \emph{improper} learning rule. The requirement of being improper is necessary as we exhibit examples of hypothesis classes $\mathcal{H}$ with finite VC dimension that are \emph{not} robustly PAC learnable with any \emph{proper} learning rule.}
}
@InProceedings{ostrovskii19a,
title = {Affine Invariant Covariance Estimation for Heavy-Tailed Distributions},
author = {Ostrovskii, Dmitrii M. and Rudi, Alessandro},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {2531--2550},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/ostrovskii19a/ostrovskii19a.pdf},
url = {http://proceedings.mlr.press/v99/ostrovskii19a.html},
abstract = {In this work we provide an estimator for the covariance matrix of a heavy-tailed multivariate distribution. We prove that the proposed estimator $\widehat{\mathbf{S}}$ admits an \textit{affine-invariant} bound of the form \[ (1-\varepsilon) \mathbf{S} \preccurlyeq \widehat{\mathbf{S}} \preccurlyeq (1+\varepsilon) \mathbf{S} \]{in} high probability, where $\mathbf{S}$ is the unknown covariance matrix, and $\preccurlyeq$ is the positive semidefinite order on symmetric matrices. The result only requires the existence of fourth-order moments, and allows for $\varepsilon = O(\sqrt{\kappa^4 d\log(d/\delta)/n})$ where $\kappa^4$ is a measure of kurtosis of the distribution, $d$ is the dimensionality of the space, $n$ is the sample size, and $1-\delta$ is the desired confidence level. More generally, we can allow for regularization with level $\lambda$, then $d$ gets replaced with the degrees of freedom number. Denoting $\text{cond}(\mathbf{S})$ the condition number of $\mathbf{S}$, the computational cost of the novel estimator is $O(d^2 n + d^3\log(\text{cond}(\mathbf{S})))$, which is comparable to the cost of the sample covariance estimator in the statistically interesing regime $n \ge d$. We consider applications of our estimator to eigenvalue estimation with relative error, and to ridge regression with heavy-tailed random design.}
}
@InProceedings{oymak19a,
title = {Stochastic Gradient Descent Learns State Equations with Nonlinear Activations},
author = {Oymak, Samet},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {2551--2579},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/oymak19a/oymak19a.pdf},
url = {http://proceedings.mlr.press/v99/oymak19a.html},
abstract = {We study discrete time dynamical systems governed by the state equation $h_{t+1}=\phi(Ah_t+Bu_t)$. Here $A,B$ are weight matrices, $\phi$ is an activation function, and $u_t$ is the input data. This relation is the backbone of recurrent neural networks (e.g. LSTMs) which have broad applications in sequential learning tasks. We utilize stochastic gradient descent to learn the weight matrices from a finite input/state trajectory $\{u_t,h_t\}_{t=0}^N$. We prove that SGD estimate linearly converges to the ground truth weights while using near-optimal sample size. Our results apply to increasing activations whose derivatives are bounded away from zero. The analysis is based on i) a novel SGD convergence result with nonlinear activations and ii) careful statistical characterization of the state vector. Numerical experiments verify the fast convergence of SGD on ReLU and leaky ReLU in consistence with our theory.}
}
@InProceedings{qiao19a,
title = {A Theory of Selective Prediction},
author = {Qiao, Mingda and Valiant, Gregory},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {2580--2594},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/qiao19a/qiao19a.pdf},
url = {http://proceedings.mlr.press/v99/qiao19a.html},
abstract = {We consider a model of selective prediction, where the prediction algorithm is given a data sequence in an online fashion and asked to predict a pre-specified statistic of the upcoming data points. The algorithm is allowed to choose when to make the prediction as well as the length of the prediction window, possibly depending on the observations so far. We prove that, even without any distributional assumption on the input data stream, a large family of statistics can be estimated to non-trivial accuracy. To give one concrete example, suppose that we are given access to an arbitrary binary sequence $x_1, \ldots, x_n$ of length $n$. Our goal is to accurately predict the average observation, and we are allowed to choose the window over which the prediction is made: for some $t < n$ and $m \le n - t$, after seeing $t$ observations we predict the average of $x_{t+1}, \ldots, x_{t+m}$. This particular problem was first studied in Drucker (2013) and referred to as the “density prediction game”. We show that the expected squared error of our prediction can be bounded by $O(\frac{1}{\log n})$ and prove a matching lower bound, which resolves an open question raised in Drucker (2013). This result holds for any sequence (that is not adaptive to when the prediction is made, or the predicted value), and the expectation of the error is with respect to the randomness of the prediction algorithm. Our results apply to more general statistics of a sequence of observations, and we highlight several open directions for future work.}
}
@InProceedings{rakhlin19a,
title = {Consistency of Interpolation with Laplace Kernels is a High-Dimensional Phenomenon},
author = {Rakhlin, Alexander and Zhai, Xiyu},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {2595--2623},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/rakhlin19a/rakhlin19a.pdf},
url = {http://proceedings.mlr.press/v99/rakhlin19a.html},
abstract = { We show that minimum-norm interpolation in the Reproducing Kernel Hilbert Space corresponding to the Laplace kernel is not consistent if input dimension is constant. The lower bound holds for any choice of kernel bandwidth, even if selected based on data. The result supports the empirical observation that minimum-norm interpolation (that is, exact fit to training data) in RKHS generalizes well for some high-dimensional datasets, but not for low-dimensional ones.}
}
@InProceedings{reeve19a,
title = {Classification with unknown class-conditional label noise on non-compact feature spaces},
author = {Reeve, Henry and Kab\'{a}n},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {2624--2651},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/reeve19a/reeve19a.pdf},
url = {http://proceedings.mlr.press/v99/reeve19a.html},
abstract = {We investigate the problem of classification in the presence of unknown class-conditional label noise in which the labels observed by the learner have been corrupted with some unknown class dependent probability. In order to obtain finite sample rates, previous approaches to classification with unknown class-conditional label noise have required that the regression function is close to its extrema on sets of large measure. We shall consider this problem in the setting of non-compact metric spaces, where the regression function need not attain its extrema. In this setting we determine the minimax optimal learning rates (up to logarithmic factors). The rate displays interesting threshold behaviour: When the regression function approaches its extrema at a sufficient rate, the optimal learning rates are of the same order as those obtained in the label-noise free setting. If the regression function approaches its extrema more gradually then classification performance necessarily degrades. In addition, we present an adaptive algorithm which attains these rates without prior knowledge of either the distributional parameters or the local density. This identifies for the first time a scenario in which finite sample rates are achievable in the label noise setting, but they differ from the optimal rates without label noise. }
}
@InProceedings{reeves19a,
title = {The All-or-Nothing Phenomenon in Sparse Linear Regression},
author = {Reeves, Galen and Xu, Jiaming and Zadik, Ilias},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {2652--2663},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/reeves19a/reeves19a.pdf},
url = {http://proceedings.mlr.press/v99/reeves19a.html},
abstract = {We study the problem of recovering a hidden binary $k$-sparse $p$-dimensional vector $\beta$ from $n$ noisy linear observations $Y=X\beta+W$ where $X_{ij}$ are i.i.d. $\mathcal{N}(0,1)$ and $W_i$ are i.i.d. $\mathcal{N}(0,\sigma^2)$. A closely related hypothesis testing problem is to distinguish the pair $(X,Y)$ generated from this structured model from a corresponding null model where $(X,Y)$ consist of purely independent Gaussian entries. In the low sparsity $k=o(p)$ and high signal to noise ratio $k/\sigma^2=\Omega\left(1\right)$ regime, we establish an “All-or-Nothing” information-theoretic phase transition at a critical sample size $n^*=2 k\log \left(p/k\right) /\log \left(1+k/\sigma^2\right)$, resolving a conjecture of [GamarnikZadik17]. Specifically, we show that if $\liminf_{p\rightarrow \infty} n/n^*>1$, then the maximum likelihood estimator almost perfectly recovers the hidden vector with high probability and moreover the true hypothesis can be detected with a vanishing error probability. Conversely, if $\limsup_{p\rightarrow \infty} n/n^*<1$, then it becomes information-theoretically impossible even to recover an arbitrarily small but fixed fraction of the hidden vector support, or to test hypotheses strictly better than random guess. Our proof of the impossibility result builds upon two key techniques, which could be of independent interest. First, we use a conditional second moment method to upper bound the Kullback-Leibler (KL) divergence between the structured and the null model. Second, inspired by the celebrated area theorem, we establish a lower bound to the minimum mean squared estimation error of the hidden vector in terms of the KL divergence between the two models.}
}
@InProceedings{safran19a,
title = {Depth Separations in Neural Networks: What is Actually Being Separated?},
author = {Safran, Itay and Eldan, Ronen and Shamir, Ohad},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {2664--2666},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/safran19a/safran19a.pdf},
url = {http://proceedings.mlr.press/v99/safran19a.html},
abstract = {Existing depth separation results for constant-depth networks essentially show that certain radial functions in $\mathbb{R}^d$, which can be easily approximated with depth $3$ networks, cannot be approximated by depth $2$ networks, even up to constant accuracy, unless their size is exponential in $d$. However, the functions used to demonstrate this are rapidly oscillating, with a Lipschitz parameter scaling polynomially with the dimension $d$ (or equivalently, by scaling the function, the hardness result applies to $\mathcal{O}(1)$-Lipschitz functions only when the target accuracy $\epsilon$ is at most $\text{poly}(1/d)$). In this paper, we study whether such depth separations might still hold in the natural setting of $\mathcal{O}(1)$-Lipschitz radial functions, when $\epsilon$ does not scale with $d$. Perhaps surprisingly, we show that the answer is negative: In contrast to the intuition suggested by previous work, it \emph{is} possible to approximate $\mathcal{O}(1)$-Lipschitz radial functions with depth $2$, size $\text{poly}(d)$ networks, for every constant $\epsilon$. We complement it by showing that approximating such functions is also possible with depth $2$, size $\text{poly}(1/\epsilon)$ networks, for every constant $d$. Finally, we show that it is not possible to have polynomial dependence in both $d,1/\epsilon$ simultaneously. Overall, our results indicate that in order to show depth separations for expressing $\mathcal{O}(1)$-Lipschitz functions with constant accuracy – if at all possible – one would need fundamentally different techniques than existing ones in the literature.}
}
@InProceedings{savarese19a,
title = {How do infinite width bounded norm networks look in function space?},
author = {Savarese, Pedro and Evron, Itay and Soudry, Daniel and Srebro, Nathan},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {2667--2690},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/savarese19a/savarese19a.pdf},
url = {http://proceedings.mlr.press/v99/savarese19a.html},
abstract = {We consider the question of what functions can be captured by ReLU networks with an unbounded number of units (infinite width), but where the overall network Euclidean norm (sum of squares of all weights in the system, except for an unregularized bias term for each unit) is bounded; or equivalently what is the minimal norm required to approximate a given function. For functions $f:\mathbb R \rightarrow\mathbb R$ and a single hidden layer, we show that the minimal network norm for representing $f$ is $\max(\int \lvert f”(x) \rvert \mathrm{d} x, \lvert f’(-\infty) + f’(+\infty) \rvert)$, and hence the minimal norm fit for a sample is given by a linear spline interpolation. }
}
@InProceedings{shamir19a,
title = {Exponential Convergence Time of Gradient Descent for One-Dimensional Deep Linear Neural Networks},
author = {Shamir, Ohad},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {2691--2713},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/shamir19a/shamir19a.pdf},
url = {http://proceedings.mlr.press/v99/shamir19a.html},
abstract = {We study the dynamics of gradient descent on objective functions of the form $f(\prod_{i=1}^{k} w_i)$ (with respect to scalar parameters $w_1,\ldots,w_k$), which arise in the context of training depth-$k$ linear neural networks. We prove that for standard random initializations, and under mild assumptions on $f$, the number of iterations required for convergence scales exponentially with the depth $k$. We also show empirically that this phenomenon can occur in higher dimensions, where each $w_i$ is a matrix. This highlights a potential obstacle in understanding the convergence of gradient-based methods for deep linear neural networks, where $k$ is large.}
}
@InProceedings{simchowitz19a,
title = {Learning Linear Dynamical Systems with Semi-Parametric Least Squares},
author = {Simchowitz, Max and Boczar, Ross and Recht, Benjamin},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {2714--2802},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/simchowitz19a/simchowitz19a.pdf},
url = {http://proceedings.mlr.press/v99/simchowitz19a.html},
abstract = {We analyze a simple prefiltered variation of the least squares estimator for the problem of estimation with biased, \emph{semi-parametric} noise, an error model studied more broadly in causal statistics and active learning. We prove an oracle inequality which demonstrates that this procedure provably mitigates the variance introduced by long-term dependencies. % We then demonstrate that prefiltered least squares yields, to our knowledge, the first algorithm that provably estimates the parameters of partially-observed linear systems that attains rates which do not not incur a worst-case dependence on the rate at which these dependencies decay. % The algorithm is provably consistent even for systems which satisfy the weaker \emph{marginal stability} condition obeyed by many classical models based on Newtonian mechanics. In this context, our semi-parametric framework yields guarantees for both stochastic and worst-case noise.}
}
@InProceedings{srikant19a,
title = {Finite-Time Error Bounds For Linear Stochastic Approximation andTD Learning},
author = {Srikant, R. and Ying, Lei},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {2803--2830},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/srikant19a/srikant19a.pdf},
url = {http://proceedings.mlr.press/v99/srikant19a.html},
abstract = {We consider the dynamics of a linear stochastic approximation algorithm driven by Markovian noise, and derive finite-time bounds on the moments of the error, i.e., deviation of the output of the algorithm from the equilibrium point of an associated ordinary differential equation (ODE). We obtain finite-time bounds on the mean-square error in the case of constant step-size algorithms by considering the drift of an appropriately chosen Lyapunov function. The Lyapunov function can be interpreted either in terms of Stein’s method to obtain bounds on steady-state performance or in terms of Lyapunov stability theory for linear ODEs. We also provide a comprehensive treatment of the moments of the square of the 2-norm of the approximation error. Our analysis yields the following results: (i) for a given step-size, we show that the lower-order moments can be made small as a function of the step-size and can be upper-bounded by the moments of a Gaussian random variable; (ii) we show that the higher-order moments beyond a threshold may be infinite in steady-state; and (iii) we characterize the number of samples needed for the finite-time bounds to be of the same order as the steady-state bounds. As a by-product of our analysis, we also solve the open problem of obtaining finite-time bounds for the performance of temporal difference learning algorithms with linear function approximation and a constant step-size, without requiring a projection step or an i.i.d. noise assumption.}
}
@InProceedings{stephan19a,
title = {Robustness of Spectral Methods for Community Detection},
author = {Stephan, Ludovic and Massouli\'{e}, Laurent},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {2831--2860},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/stephan19a/stephan19a.pdf},
url = {http://proceedings.mlr.press/v99/stephan19a.html},
abstract = {The present work is concerned with community detection. Specifically, we consider a random graph drawn according to the stochastic block model: its vertex set is partitioned into blocks, or communities, and edges are placed randomly and independently of each other with probability depending only on the communities of their two endpoints. In this context, our aim is to recover the community labels better than by random guess, based only on the observation of the graph. In the sparse case, where edge probabilities are in $O(1/n)$, we introduce a new spectral method based on the distance matrix $D^{(\ell)}$, where $D^{(\ell)}_{ij} = 1$ iff the graph distance between $i$ and $j$, noted $d(i, j)$ is equal to $\ell$. We show that when $\ell \sim c\log(n)$ for carefully chosen $c$, the eigenvectors associated to the largest eigenvalues of $D^{(\ell)}$ provide enough information to perform non-trivial community recovery with high probability, provided we are above the so-called Kesten-Stigum threshold. This yields an efficient algorithm for community detection, since computation of the matrix $D^{(\ell)}$ can be done in $O(n^{1+\kappa})$ operations for a small constant $\kappa$. We then study the sensitivity of the eigendecomposition of $D^{(\ell)}$ when we allow an adversarial perturbation of the edges of $G$. We show that when the considered perturbation does not affect more than $O(n^\varepsilon)$ vertices for some small $\varepsilon > 0$, the highest eigenvalues and their corresponding eigenvectors incur negligible perturbations, which allows us to still perform efficient recovery. Our proposed spectral method therefore: i) is robust to larger perturbations than prior spectral methods, while semi-definite programming (or SDP) methods can tolerate yet larger perturbations; ii) achieves non-trivial detection down to the KS threshold, which is conjectured to be optimal and is beyond reach of existing SDP approaches; iii) is faster than SDP approaches.}
}
@InProceedings{straszak19a,
title = {Maximum Entropy Distributions: Bit Complexity and Stability},
author = {Straszak, Damian and Vishnoi, Nisheeth K.},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {2861--2891},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/straszak19a/straszak19a.pdf},
url = {http://proceedings.mlr.press/v99/straszak19a.html},
abstract = {Maximum entropy distributions with discrete support in $m$ dimensions arise in machine learning, statistics, information theory, and theoretical computer science. While structural and computational properties of max-entropy distributions have been extensively studied, basic questions such as: Do max-entropy distributions over a large support (e.g., $2^m$) with a specified marginal vector have succinct descriptions (polynomial-size in the input description)? and: Are entropy maximizing distributions “stable” under the perturbation of the marginal vector? have resisted a rigorous resolution. Here we show that these questions are related and resolve both of them. Our main result shows a ${\rm poly}(m, \log 1/\varepsilon)$ bound on the bit complexity of $\varepsilon$-optimal dual solutions to the maximum entropy convex program – for very general support sets and with no restriction on the marginal vector. Applications of this result include polynomial time algorithms to compute max-entropy distributions over several new and old polytopes for any marginal vector in a unified manner, a polynomial time algorithm to compute the Brascamp-Lieb constant in the rank-1 case. The proof of this result allows us to show that changing the marginal vector by $\delta$ changes the max-entropy distribution in the total variation distance roughly by a factor of ${\rm poly}(m, \log 1/\delta)\sqrt{\delta}$ – even when the size of the support set is exponential. Together, our results put max-entropy distributions on a mathematically sound footing – these distributions are robust and computationally feasible models for data.}
}
@InProceedings{suggala19a,
title = {Adaptive Hard Thresholding for Near-optimal Consistent Robust Regression},
author = {Suggala, Arun Sai and Bhatia, Kush and Ravikumar, Pradeep and Jain, Prateek},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {2892--2897},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/suggala19a/suggala19a.pdf},
url = {http://proceedings.mlr.press/v99/suggala19a.html},
abstract = {We study the problem of robust linear regression with response variable corruptions. We consider the oblivious adversary model, where the adversary corrupts a fraction of the responses in complete ignorance of the data. We provide a nearly linear time estimator which consistently estimates the true regression vector, even with $1-o(1)$ fraction of corruptions. Existing results in this setting either don’t guarantee consistent estimates or can only handle a small fraction of corruptions. We also extend our estimator to robust sparse linear regression and show that similar guarantees hold in this setting. Finally, we apply our estimator to the problem of linear regression with heavy-tailed noise and show that our estimator consistently estimates the regression vector even when the noise has unbounded variance (e.g., Cauchy distribution), for which most existing results don’t even apply. Our estimator is based on a novel variant of outlier removal via hard thresholding in which the threshold is chosen adaptively and crucially relies on randomness to escape bad fixed points of the non-convex hard thresholding operation.}
}
@InProceedings{sun19a,
title = {Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches},
author = {Sun, Wen and Jiang, Nan and Krishnamurthy, Akshay and Agarwal, Alekh and Langford, John},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {2898--2933},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/sun19a/sun19a.pdf},
url = {http://proceedings.mlr.press/v99/sun19a.html},
abstract = {We study the sample complexity of model-based reinforcement learning (henceforth RL) in general contextual decision processes that require strategic exploration to find a near-optimal policy. We design new algorithms for RL with a generic model class and analyze their statistical properties. Our algorithms have sample complexity governed by a new structural parameter called the witness rank, which we show to be small in several settings of interest, including factored MDPs. We also show that the witness rank is never larger than the recently proposed Bellman rank parameter governing the sample complexity of the model-free algorithm OLIVE (Jiang et al., 2017), the only other provably sample-efficient algorithm for global exploration at this level of generality. Focusing on the special case of factored MDPs, we prove an exponential lower bound for a general class of model-free approaches, including OLIVE, which, when combined with our algorithmic results, demonstrates exponential separation between model-based and model-free RL in some rich-observation settings.}
}
@InProceedings{taylor19a,
title = {Stochastic first-order methods: non-asymptotic and computer-aided analyses via potential functions},
author = {Taylor, Adrien and Bach, Francis},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {2934--2992},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/taylor19a/taylor19a.pdf},
url = {http://proceedings.mlr.press/v99/taylor19a.html},
abstract = {We provide a novel computer-assisted technique for systematically analyzing first-order methods for optimization. In contrast with previous works, the approach is particularly suited for handling sublinear convergence rates and stochastic oracles. The technique relies on semidefinite programming and potential functions. It allows simultaneously obtaining worst-case guarantees on the behavior of those algorithms, and assisting in choosing appropriate parameters for tuning their worst-case performances. The technique also benefits from comfortable tightness guarantees, meaning that unsatisfactory results can be improved only by changing the setting. We use the approach for analyzing deterministic and stochastic first-order methods under different assumptions on the nature of the stochastic noise. Among others, we treat unstructured noise with bounded variance, different noise models arising in over-parametrized expectation minimization problems, and randomized block-coordinate descent schemes.}
}
@InProceedings{tosh19a,
title = {The Relative Complexity of Maximum Likelihood Estimation, MAP Estimation, and Sampling},
author = {Tosh, Christopher and Dasgupta, Sanjoy},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {2993--3035},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/tosh19a/tosh19a.pdf},
url = {http://proceedings.mlr.press/v99/tosh19a.html},
abstract = {We prove that, for a broad range of problems, maximum-a-posteriori (MAP) estimation and approximate sampling of the posterior are at least as computationally difficult as maximum-likelihood (ML) estimation. By way of illustration, we show how hardness results for ML estimation of mixtures of Gaussians and topic models carry over to MAP estimation and approximate sampling under commonly used priors.}
}
@InProceedings{tu19a,
title = {The Gap Between Model-Based and Model-Free Methods on the Linear Quadratic Regulator: An Asymptotic Viewpoint},
author = {Tu, Stephen and Recht, Benjamin},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {3036--3083},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/tu19a/tu19a.pdf},
url = {http://proceedings.mlr.press/v99/tu19a.html},
abstract = {The effectiveness of model-based versus model-free methods is a long-standing question in reinforcement learning (RL). Motivated by recent empirical success of RL on continuous control tasks, we study the sample complexity of popular model-based and model-free algorithms on the Linear Quadratic Regulator (LQR). We show that for policy evaluation, a simple model-based plugin method requires asymptotically less samples than the classical least-squares temporal difference (LSTD) estimator to reach the same quality of solution; the sample complexity gap between the two methods can be at least a factor of state dimension. For policy optimization, we study a simple family of problem instances and show that nominal (certainty equivalence principle) control also requires several factors of state and input dimension fewer samples than the policy gradient method to reach the same level of control performance on these instances. Furthermore, the gap persists even when employing baselines commonly used in practice. To the best of our knowledge, this is the first theoretical result which demonstrates a separation in the sample complexity between model-based and model-free methods on a continuous control task.}
}
@InProceedings{tzen19a,
title = {Theoretical guarantees for sampling and inference in generative models with latent diffusions},
author = {Tzen, Belinda and Raginsky, Maxim},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {3084--3114},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/tzen19a/tzen19a.pdf},
url = {http://proceedings.mlr.press/v99/tzen19a.html},
abstract = {We introduce and study a class of probabilistic generative models, where the latent object is a finite-dimensional diffusion process on a finite time interval and the observed variable is drawn conditionally on the terminal point of the diffusion. We make the following contributions: We provide a unified viewpoint on both sampling and variational inference in such generative models through the lens of stochastic control. We quantify the expressiveness of diffusion-based generative models. Specifically, we show that one can efficiently sample from a wide class of terminal target distributions by choosing the drift of the latent diffusion from the class of multilayer feedforward neural nets, with the accuracy of sampling measured by the Kullback–Leibler divergence to the target distribution. Finally, we present and analyze a scheme for unbiased simulation of generative models with latent diffusions and provide bounds on the variance of the resulting estimators. This scheme can be implemented as a deep generative model with a random number of layers. }
}
@InProceedings{vempala19a,
title = {Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Bounds},
author = {Vempala, Santosh and Wilmes, John},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {3115--3117},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/vempala19a/vempala19a.pdf},
url = {http://proceedings.mlr.press/v99/vempala19a.html},
abstract = {We study the complexity of training neural network models with one hidden nonlinear activation layer and an output weighted sum layer. We analyze Gradient Descent applied to learning a bounded target function on $n$ real-valued inputs. %by training a neural network with a single hidden layer of nonlinear gates. We give an agnostic learning guarantee for GD: starting from a randomly initialized network, it converges in mean squared loss to the minimum error (in $2$-norm) of the best approximation of the target function using a polynomial of degree at most $k$. Moreover, for any $k$, the size of the network and number of iterations needed are both bounded by $n^{O(k)}\log(1/\epsilon)$. The core of our analysis is the following existence theorem, which is of independent interest: for any $\epsilon > 0$, any bounded function that has a degree $k$ polynomial approximation with error $\epsilon_0$ (in $2$-norm), can be approximated to within error $\epsilon_0 + \epsilon$ as a linear combination of $n^{O(k)}\cdot \mbox{poly}(1/\epsilon)$ {\em randomly chosen} gates from any class of gates whose corresponding activation function has nonzero coefficients in its harmonic expansion for degrees up to $k$. In particular, this applies to training networks of unbiased sigmoids and ReLUs. We also rigorously explain the empirical finding that gradient descent discovers lower frequency Fourier components before higher frequency components. We complement this result with nearly matching lower bounds in the Statistical Query model. GD fits well in the SQ framework since each training step is determined by an expectation over the input distribution. We show that any SQ algorithm that achieves significant improvement over a constant function with queries of tolerance some inverse polynomial in the input dimensionality $n$ must use $n^{\Omega(k)}$ queries even when the target functions are restricted to a set of $n^{O(k)}$ degree-$k$ polynomials, and the input distribution is uniform over the unit sphere; for this class the information-theoretic lower bound is only $\Theta(k \log n)$. Our approach for both parts is based on spherical harmonics. We view gradient descent as an operator on the space of functions, and study its dynamics. An essential tool is the Funk-Hecke theorem, which explains the eigenfunctions of this operator in the case of the mean squared loss.}
}
@InProceedings{weed19a,
title = {Estimation of smooth densities in Wasserstein distance},
author = {Weed, Jonathan and Berthet, Quentin},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {3118--3119},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/weed19a/weed19a.pdf},
url = {http://proceedings.mlr.press/v99/weed19a.html},
abstract = {The Wasserstein distances are a set of metrics on probability distributions supported on $\mathbb{R}^d$ with applications throughout statistics and machine learning. Often, such distances are used in the context of variational problems, in which the statistician employs in place of an unknown measure a proxy constructed on the basis of independent samples. This raises the basic question of how well measures can be approximated in Wasserstein distance. While it is known that an empirical measure comprising i.i.d. samples is rate-optimal for general measures, no improved results were known for measures possessing smooth densities. We prove the first minimax rates for estimation of smooth densities for general Wasserstein distances, thereby showing how the curse of dimensionality can be alleviated for sufficiently regular measures. We also show how to construct discretely supported measures, suitable for computational purposes, which enjoy improved rates. Our approach is based on novel bounds between the Wasserstein distances and suitable Besov norms, which may be of independent interest.}
}
@InProceedings{wolfer19a,
title = {Estimating the Mixing Time of Ergodic Markov Chains},
author = {Wolfer, Geoffrey and Kontorovich, Aryeh},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {3120--3159},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/wolfer19a/wolfer19a.pdf},
url = {http://proceedings.mlr.press/v99/wolfer19a.html},
abstract = {We address the problem of estimating the mixing time $t_{\mathsf{mix}}$ of an arbitrary ergodic finite Markov chain from a single trajectory of length $m$. The reversible case was addressed by Hsu et al. [2018+], who left the general case as an open problem. In the reversible case, the analysis is greatly facilitated by the fact that the Markov operator is self-adjoint, and Weyl’s inequality allows for a dimension-free perturbation analysis of the empirical eigenvalues. As Hsu et al. point out, in the absence of reversibility (and hence, the non-symmetry of the pair probabilities matrix), the existing perturbation analysis has a worst-case exponential dependence on the number of states $d$. Furthermore, even if an eigenvalue perturbation analysis with better dependence on $d$ were available, in the non-reversible case the connection between the spectral gap and the mixing time is not nearly as straightforward as in the reversible case. Our key insight is to estimate the pseudo-spectral gap instead, which allows us to overcome the loss of self-adjointness and to achieve a polynomial dependence on $d$ and the minimal stationary probability $\pi_\star$. Additionally, in the reversible case, we obtain simultaneous nearly (up to logarithmic factors) minimax rates in $t_{\mathsf{mix}}$ and precision $\varepsilon$, closing a gap in Hsu et al., who treated $\varepsilon$ as constant in the lower bounds. Finally, we construct fully empirical confidence intervals for the pseudo-spectral gap, which shrink to zero at a rate of roughly $1/\sqrt m$, and improve the state of the art in even the reversible case.}
}
@InProceedings{zhang19a,
title = {Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the $O(1/T)$ Convergence Rate},
author = {Zhang, Lijun and Zhou, Zhi-Hua},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {3160--3179},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/zhang19a/zhang19a.pdf},
url = {http://proceedings.mlr.press/v99/zhang19a.html},
abstract = {Stochastic approximation (SA) is a classical approach for stochastic convex optimization. Previous studies have demonstrated that the convergence rate of SA can be improved by introducing either smoothness or strong convexity condition. In this paper, we make use of smoothness and strong convexity simultaneously to boost the convergence rate. Let $\lambda$ be the modulus of strong convexity, $\kappa$ be the condition number, $F_*$ be the minimal risk, and $\alpha>1$ be some small constant. First, we demonstrate that, in expectation, an $O(1/[\lambda T^\alpha] + \kappa F_*/T)$ risk bound is attainable when $T = \Omega(\kappa^\alpha)$. Thus, when $F_*$ is small, the convergence rate could be faster than $O(1/[\lambda T])$ and approaches $O(1/[\lambda T^\alpha])$ in the ideal case. Second, to further benefit from small risk, we show that, in expectation, an $O(1/2^{T/\kappa}+F_*)$ risk bound is achievable. Thus, the excess risk reduces exponentially until reaching $O(F_*)$, and if $F_*=0$, we obtain a global linear convergence. Finally, we emphasize that our proof is constructive and each risk bound is equipped with an efficient stochastic algorithm attaining that bound.}
}
@InProceedings{daniely19a,
title = {Open Problem: Is Margin Sufficient for Non-Interactive Private Distributed Learning?},
author = {Daniely, Amit and Feldman, Vitaly},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {3180--3184},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/daniely19a/daniely19a.pdf},
url = {http://proceedings.mlr.press/v99/daniely19a.html},
abstract = {We ask whether every class of Boolean functions that has polynomial margin complexity can be PAC learned efficiently by a non-interactive locally differentially private algorithm.}
}
@InProceedings{feldman19b,
title = {Open Problem: How fast can a multiclass test set be overfit?},
author = {Feldman, Vitaly and Frostig, Roy and Hardt, Moritz},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {3185--3189},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/feldman19b/feldman19b.pdf},
url = {http://proceedings.mlr.press/v99/feldman19b.html},
abstract = {We ask how many measurements of the accuracy on a multiclass benchmark are needed to achieve a given amount of overfitting.}
}
@InProceedings{ge19b,
title = {Open Problem: Do Good Algorithms Necessarily Query Bad Points?},
author = {Ge, Rong and Jain, Prateek and Kakade, Sham M. and Kidambi, Rahul and Nagaraj, Dheeraj M. and Netrapalli, Praneeth},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {3190--3193},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/ge19b/ge19b.pdf},
url = {http://proceedings.mlr.press/v99/ge19b.html},
abstract = {Folklore results in the theory of Stochastic Approximation indicates the (minimax) optimality of Stochastic Gradient Descent (SGD) (Robbins and Monro, 1951) with polynomially decaying stepsizes and iterate averaging (Ruppert, 1988; Polyak and Juditsky, 1992) for classes of stochastic convex optimization. Basing of these folkore results and some recent developments, this manuscript considers a more subtle question: does any algorithm necessarily (information theoretically) have to query iterates that are sub-optimal infinitely often?}
}
@InProceedings{perotto19a,
title = {Open Problem: Risk of Ruin in Multiarmed Bandits},
author = {Perotto, Filipo S. and Bourgais, Mathieu and Silva, Bruno C. and Vercouter, Laurent},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {3194--3197},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/perotto19a/perotto19a.pdf},
url = {http://proceedings.mlr.press/v99/perotto19a.html},
abstract = {We formalize a particular class of problems called \textit{survival multiarmed bandits} (S-MAB), which constitutes a modified version of \textit{budgeted multiarmed bandits} (B-MAB) where a true \textit{risk of ruin} must be considered, bringing it closer to \textit{risk-averse multiarmed bandits} (RA-MAB). In a S-MAB, pulling an arm can result in both positive and negative rewards. The agent has an initial budget that evolves in time with the received rewards. The goal is finding a good \textit{exploration-exploitation-safety} trade-off, maximizing rewards while minimizing the probability of getting ruined (i.e. hitting a negative budget). Such simple and until now neglected modification in the MAB statement changes the way to approach the problem, asking for adapted algorithms and specific analytical tools, and also make it more likely related to some important real-world applications. We are interested in the following open problems which stem from such new MAB definition: (a) how can the regret be meaningfully defined in formal terms for a S-MAB given its multiobjective optimization nature? (b) can a S-MAB be reduced to a RA-MAB or a B-MAB, transferring their theoretical guarantees? (c) what kind of method or strategy must an agent follow to optimally solve a S-MAB?}
}
@InProceedings{viering19a,
title = {Open Problem: Monotonicity of Learning},
author = {Viering, Tom and Mey, Alexander and Loog, Marco},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {3198--3201},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/viering19a/viering19a.pdf},
url = {http://proceedings.mlr.press/v99/viering19a.html},
abstract = {We pose the question to what extent a learning algorithm behaves monotonically in the following sense: does it perform better, in expectation, when adding one instance to the training set? We focus on empirical risk minimization and illustrate this property with several examples, two where it does hold and two where it does not. We also relate it to the notion of PAC-learnability.}
}
@InProceedings{woodworth19a,
title = {Open Problem: The Oracle Complexity of Convex Optimization with Limited Memory},
author = {Woodworth, Blake and Srebro, Nathan},
booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
pages = {3202--3210},
year = {2019},
editor = {Beygelzimer, Alina and Hsu, Daniel},
volume = {99},
series = {Proceedings of Machine Learning Research},
address = {Phoenix, USA},
month = {25--28 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v99/woodworth19a/woodworth19a.pdf},
url = {http://proceedings.mlr.press/v99/woodworth19a.html},
abstract = {We note that known methods achieving the optimal oracle complexity for first order convex optimization require quadratic memory, and ask whether this is necessary, and more broadly seek to characterize the minimax number of first order queries required to optimize a convex Lipschitz function subject to a memory constraint.}
}