Distributionally robust optimization hedges a decision against an ambiguity set of candidate distributions. In a cold-start setting the target distribution is unobserved and no sample from it is available, so only related source distributions provide evidence for constructing that set. We propose an inclusive-exclusive Wasserstein ball model that jointly learns a center and radius from … Read more
We study stochastic optimization with a completely unobserved target distribution and samples from related source distributions. Treating the sources and the target as independent draws from a common meta-distribution, we propose Wasserstein-metric meta-distribution support learning (MDSL). The model jointly learns the center and radius of a Wasserstein ball, with an exclusion parameter controlling the fraction … Read more
Stochastic Gradient Descent (\(\textsf{SGD}\)) is one of the most classical optimization algorithms with favorable theoretical guarantees, yet its practical implementation differs subtly from its well-known form and is often referred to as Shuffling Stochastic Gradient Descent (\(\textsf{Shuffling SGD}\)). A particularly popular strategy in \(\textsf{Shuffling SGD}\) is Random Reshuffling (\(\textsf{RR}\)), which has achieved great empirical success. … Read more
Decision scenarios far from rare in practice often place data-driven decision-making in an awkward position, where the decision maker may have access to neither the target distribution itself nor any empirical samples drawn from it, especially when decisions must be made in novel or highly uncertain environments. In response, robust out-of-distribution stochastic optimization (RooDSO) has … Read more
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
We introduce the concept of disjunctive sum of squares for certifying nonnegativity of polynomials. Unlike the popular sum of squares approach where nonnegativity is certified by a single algebraic identity, the disjunctive sum of squares approach certifies nonnegativity with multiple algebraic identities which can be found in parallel. Our main result is a disjunctive Positivstellensatz … Read more
In this work, we study optimization specified only through a comparison oracle: given two points, it reports which one is preferred. We call it function-free optimization because we do not assume access to, nor the existence of, a canonical application-given objective function. Instead, our goal is to find a most-preferred feasible point, which we call … Read more
Large-scale problems in data science are often modeled with optimization and solved with first-order methods that may converge at a sublinear rate. It is of interest to terminate the optimization algorithm as soon as the underlying data science task is accomplished. We analyze the complexity of first-order methods for support vector machines (SVMs) in terms … Read more
We present a performant gradient method for smooth convex optimization, drawing inspiration from several recent advances in the field. Our algorithm, the Adaptive Subgame Perfect Gradient Method (ASPGM) is based on the notion of subgame perfection, attaining a dynamic strengthening of minimax optimality. At each iteration, ASPGM makes a momentum-type update, optimized dynamically based on … Read more
We propose a first order algorithm, a modified version of FISTA, to solve an optimization problem with an objective function that is the sum of a possibly nonconvex function, with Lipschitz continuous gradient, and a convex function which can be nonsmooth. The algorithm is shown to have an iteration complexity of \(\mathcal{O}(\epsilon^{-2})\) to find an … Read more