Papers

In many real-world problems, first-order (FO) derivative evaluations are too expensive or even inaccessible. For solving these problems, zeroth-order (ZO) methods that only need function evaluations are often more efficient than FO methods or sometimes the only options. In this paper, we propose a novel zeroth-order inexact augmented Lagrangian method (ZO-iALM) to solve black-box optimization problems, which involve a composite (i.e., smooth+nonsmooth) objective and functional constraints. Under a certain regularity condition (also assumed by several existing works on FO methods), the query complexity of our ZO-iALM is $\tilde{O}(d\vareps^{-3})$ to find an $\vareps$-KKT point for problems with a nonconvex objective and nonconvex constraints, and $\tilde{O}(d\vareps^{-\frac{5}{2}})$ for nonconvex problems with convex constraints, where $d$ is the variable dimension. This appears to be the first work that develops an iALM-based ZO method for functional constrained optimization and meanwhile achieves query complexity results matching the best-known FO complexity results up to a factor of $d$. With an extensive experimental study, we show the effectiveness of our method. The applications of our method span from classical optimization problems to practical machine learning examples such as resource allocation in sensor networks and adversarial example generation.

poster session 5 @ blue 2, poster session 10 @ blue 2, oral session 10 @ blue 2, poster session 5, poster session 10, oral session 10

The goal of Approximate Query Processing (AQP) techniques is to provide very fast but “accurate enough” results for costly aggregate queries thereby improving user experience in interactive exploration of large datasets. Recently proposed ML-based AQP techniques can provide very low latency as query execution only involves model inference as compared to traditional query processing on database clusters. However, with increase in the number of filtering predicates (WHERE clauses), the approximation error significantly increases for these methods. Analysts often use queries with a large number of predicates for insights discovery. Thus, maintaining low approximation error is important to prevent analysts from drawing misleading conclusions. In this paper, we propose ELECTRA, a predicate-aware AQP system that can answer analytics-style queries with a large number of predicates with much smaller approximation errors. ELECTRA uses a conditional generative model that learns the conditional distribution of the data and at run-time generates a small (≈1000) but representative sample, on which the query is executed to compute the approximate result. Our evaluations with four different baselines on three real-world datasets show that ELECTRA provides not only lower AQP error but also can efficiently run at the client-side with low latency.

poster session 5 @ blue 2, poster session 10 @ blue 2, oral session 10 @ blue 2, poster session 5, poster session 10, oral session 10

We develop new adaptive algorithms for variational inequalities with monotone operators, which capture many problems of interest, notably convex optimization and convex-concave saddle point problems. Our algorithms automatically adapt to unknown problem parameters such as the smoothness and the norm of the operator, and the variance of the stochastic evaluation oracle. We show that our algorithms are universal and simultaneously achieve the optimal convergence rates in the non-smooth, smooth, and stochastic settings. The convergence guarantees of our algorithms improve over existing adaptive methods by a $\Omega(\sqrt{\ln T})$ factor, matching the optimal non-adaptive algorithms. Additionally, prior works require that the optimization domain is bounded. In this work, we remove this restriction and give algorithms for unbounded domains that are adaptive and universal. Our general proof techniques can be used for many variants of the algorithm using one or two operator evaluations per iteration. The classical methods based on the ExtraGradient/MirrorProx algorithm require two operator evaluations per iteration, which is the dominant factor in the running time in many settings.

poster session 5 @ blue 2, poster session 10 @ blue 2, oral session 10 @ blue 2, poster session 5, poster session 10, oral session 10