Yue Gao

Yue Gao, Garvesh Raskutti

Network estimation from multi-variate point process or time series data is a problem of fundamental importance. Prior work has focused on parametric approaches that require a known parametric model, which makes estimation procedures less robust to model mis-specification, non-linearities and heterogeneities. In this paper, we develop a semi-parametric approach based on the monotone single-index multi-variate autoregressive model (SIMAM) which addresses these challenges. We provide theoretical guarantees for dependent data and an alternating projected gradient descent algorithm. Significantly we do not explicitly assume mixing conditions on the process (although we do require conditions analogous to restricted strong convexity) and we achieve rates of the form $O(T^{-\frac{1}{3}} \sqrt{s\log(TM)})$ (optimal in the independent design case) where $s$ is the threshold for the maximum in-degree of the network that indicates the sparsity level, $M$ is the number of actors and $T$ is the number of time points. In addition, we demonstrate the superior performance both on simulated data and two real data examples where our SIMAM approach out-performs state-of-the-art parametric methods both in terms of prediction and network estimation.

Jincheng Mei, Yue Gao, Bo Dai et al.

Classical global convergence results for first-order methods rely on uniform smoothness and the Łojasiewicz inequality. Motivated by properties of objective functions that arise in machine learning, we propose a non-uniform refinement of these notions, leading to \emph{Non-uniform Smoothness} (NS) and \emph{Non-uniform Łojasiewicz inequality} (NŁ). The new definitions inspire new geometry-aware first-order methods that are able to converge to global optimality faster than the classical $Ω(1/t^2)$ lower bounds. To illustrate the power of these geometry-aware methods and their corresponding non-uniform analysis, we consider two important problems in machine learning: policy gradient optimization in reinforcement learning (PG), and generalized linear model training in supervised learning (GLM). For PG, we find that normalizing the gradient ascent method can accelerate convergence to $O(e^{-t})$ while incurring less overhead than existing algorithms. For GLM, we show that geometry-aware normalized gradient descent can also achieve a linear convergence rate, which significantly improves the best known results. We additionally show that the proposed geometry-aware descent methods escape landscape plateaus faster than standard gradient descent. Experimental results are used to illustrate and complement the theoretical findings.

Yue Gao, Or Sheffet

We give the first differentially private algorithms that estimate a variety of geometric features of points in the Euclidean space, such as diameter, width, volume of convex hull, min-bounding box, min-enclosing ball etc. Our work relies heavily on the notion of \emph{Tukey-depth}. Instead of (non-privately) approximating the convex-hull of the given set of points $P$, our algorithms approximate the geometric features of the $κ$-Tukey region induced by $P$ (all points of Tukey-depth $κ$ or greater). Moreover, our approximations are all bi-criteria: for any geometric feature $μ$ our $(α,Δ)$-approximation is a value "sandwiched" between $(1-α)μ(D_P(κ))$ and $(1+α)μ(D_P(κ-Δ))$. Our work is aimed at producing a \emph{$(α,Δ)$-kernel of $D_P(κ)$}, namely a set $\mathcal{S}$ such that (after a shift) it holds that $(1-α)D_P(κ)\subset \mathsf{CH}(\mathcal{S}) \subset (1+α)D_P(κ-Δ)$. We show that an analogous notion of a bi-critera approximation of a directional kernel, as originally proposed by Agarwal et al~[2004], \emph{fails} to give a kernel, and so we result to subtler notions of approximations of projections that do yield a kernel. First, we give differentially private algorithms that find $(α,Δ)$-kernels for a "fat" Tukey-region. Then, based on a private approximation of the min-bounding box, we find a transformation that does turn $D_P(κ)$ into a "fat" region \emph{but only if} its volume is proportional to the volume of $D_P(κ-Δ)$. Lastly, we give a novel private algorithm that finds a depth parameter $κ$ for which the volume of $D_P(κ)$ is comparable to $D_P(κ-Δ)$. We hope this work leads to the further study of the intersection of differential privacy and computational geometry.