Optimization in Data Science

Generative Neural Networks for Sinkhorn Distributionally Robust Hypothesis Testing

Categories Infinite Dimensional Optimization, Optimization in Data Science, Robust Optimization

This paper studies the Sinkhorn distributionally robust hypothesis testing (SDRHT) problem, seeking a robust detector against least-favorable distributions in Sinkhorn discrepancy-based ambiguity sets centered at the empirical distributions. Existing approaches solve this problem by solving large-scale conic programs, which are not scalable. To overcome this, we propose a generative framework that learns least-favorable distributions and … Read more

A Local-Linearly Convergent Algorithm for Nonconvex Equality-Constrained Optimization

Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Optimization in Data Science

For solving nonconvex equality-constrained optimization problems, a recent Gradient-Eigenstep Algorithm by Goyens et al.~is an iteration-efficient approach, based on minimizing Fletcher’s augmented Lagrangian function, for finding an approximate second-order stationary point from an arbitrary starting point. In this paper, the analysis of this algorithm is extended, offering a two-fold contribution. First, it is shown that … Read more

Entropy-Smooth Convex Optimization Cannot Be Accelerated

Categories Convex and Nonsmooth Optimization, Convex Optimization, Optimization in Data Science Tags , ,

We prove an $\Omega(L/T)$ lower bound for the convergence rate of minimization in the class of functions that are convex and $L$-smooth relative to negative entropy on the standard $d$-simplex, valid for every first-order method when $d = \Omega(T^2)$. In particular, this shows that mirror descent is optimal up to a logarithmic factor in this … Read more

Symmetry-Compatible Matrix-Gradient Methods: Equivariant Updates, Spectral Operators, and Convergence

Categories Data Science Algorithms, Data Science Applications, Optimization in Data Science Tags , , , ,

We develop a symmetry-compatible framework for first-order methods on matrix optimization problems. The central principle is that the update rule for a matrix variable should be equivariant with respect to the natural symmetry group acting on that variable. For matrix representations of linear operators, this leads to bi-orthogonal equivariance under left and right orthogonal changes … Read more

Order-2 Tightness of Block-Sparse SOS Relaxations for One-Layer ReLU Network Verification with a Matching Input-Sharing Graph

Categories Data Science Theory, Quadratic Programming, Semi-definite Programming Tags , , , ,

Azuma, Kim, and Yamashita formulated the verification problem for one-layer ReLU networks as a quadratically constrained quadratic program and established tight semidefinite relaxations for the edgeless case and for one-unit settings. In this work, we represent the sharing pattern of undecided ReLUs over a box input set through an input-sharing graph and focus on the … Read more

Accelerated Kernel Stein Discrepancy with Rényi Landmark Selection for GAN Training

Categories Data Science Algorithms

Our project investigates replacing the classical adversarial discriminator in GAN training with a kernel-based distance metric, namely Kernel Stein Discrepancy (KSD). We assess whether a kernelized objective can improve training stability and efficiency without compromising sample quality, and we evaluate accelerated Nystrom approximations with Renyi landmark selection on CIFAR-10. ArticleDownload View PDF

bAdag: an adaptive block coordinate gradient method for smooth nonconvex functions

Categories Data Science Algorithms, Unconstrained Optimization Tags , , ,

A new Block Coordinate Gradient (BCG) method, dubbed bAdag, for smooth, nonconvex minimization problem is proposed; it falls in the class of Objective Function Free Optimization (OFFO) methods, and it is based on the AdaGrad algorithm. At each iteration, our method computes an adaptive step size based on the cumulative sum of block gradients, instead … Read more

Constrained Variable Projection for Structured Problems

Categories Bilevel Optimization, Nonlinear Optimization, Optimization in Data Science Tags , ,

Variable projection is a classical technique for separable nonlinear least-squares problems, in which variables that enter linearly are eliminated exactly, yielding a reduced nonlinear problem. By expressing this framework as a particular instance of a broader class of bilevel optimization problems, we develop a constrained variable-projection framework for data-science models, where the remaining variables are … Read more

D-optimal partitioning: design of experiments under heterogeneous treatment effects

Categories Combinatorial Optimization, Nonlinear Optimization, Optimization in Data Science Tags , , , ,

Modern experimentation in business and public policy often studies targeted interventions whose effects depend on the heterogeneous attributes of individuals. We examine heterogeneous treatment effects through the lens of optimal design of experiments, which allocates treatment decisions to maximize the precision of estimated treatment-covariate interactions. We introduce the D-optimal partitioning problem for balancing the information … Read more

Stochastic convergence of parallel asynchronous adaptive first-order methods

Categories Data Science Algorithms, Stochastic Programming, Unconstrained Optimization Tags , , , , ,

A new class of asynchronous adaptive first-order optimization methods is introduced, comprising asynchronous variants of several popular algorithms. Versions of these methods using momentum and/or inexact normalization are also considered. The convergence of methods in the class on non-convex functions is analyzed in a fully stochastic setting, and is shown to be (up to logarithmic … Read more