Source author record

Jasper C. H. Lee

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Machine Learning Data Structures and Algorithms Artificial Intelligence math.OC Information Theory math.IT math.ST Statistics Theory

Catalog footprint

Research overview

5works

8topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Branch & Learn for Recursively and Iteratively Solvable Problems in Predict+Optimize

This paper proposes Branch & Learn, a framework for Predict+Optimize to tackle optimization problems containing parameters that are unknown at the time of solving. Given an optimization problem solvable by a recursive algorithm satisfying simple conditions, we show how a corresponding learning algorithm can be constructed directly and methodically from the recursive algorithm. Our framework applies also to iterative algorithms by viewing them as a degenerate form of recursion. Extensive experimentation shows better performance for our proposal over classical and state-of-the-art approaches.

preprint2022arXiv

Finite-Sample Maximum Likelihood Estimation of Location

We consider 1-dimensional location estimation, where we estimate a parameter $λ$ from $n$ samples $λ+ η_i$ , with each $η_i$ drawn i.i.d. from a known distribution $f$ . For fixed $f$ the maximum-likelihood estimate (MLE) is well-known to be optimal in the limit as $n \to \infty$ : it is asymptotically normal with variance matching the Cramér-Rao lower bound of $\frac{1}{n\mathcal{I}}$ , where $\mathcal{I}$ is the Fisher information of $f$ . However, this bound does not hold for finite $n$ , or when $f$ varies with $n$ . We show for arbitrary $f$ and $n$ that one can recover a similar theory based on the Fisher information of a smoothed version of $f$ , where the smoothing radius decays with $n$ .

preprint2022arXiv

Predict+Optimize for Packing and Covering LPs with Unknown Parameters in Constraints

Predict+Optimize is a recently proposed framework which combines machine learning and constrained optimization, tackling optimization problems that contain parameters that are unknown at solving time. The goal is to predict the unknown parameters and use the estimates to solve for an estimated optimal solution to the optimization problem. However, all prior works have focused on the case where unknown parameters appear only in the optimization objective and not the constraints, for the simple reason that if the constraints were not known exactly, the estimated optimal solution might not even be feasible under the true parameters. The contributions of this paper are two-fold. First, we propose a novel and practically relevant framework for the Predict+Optimize setting, but with unknown parameters in both the objective and the constraints. We introduce the notion of a correction function, and an additional penalty term in the loss function, modelling practical scenarios where an estimated optimal solution can be modified into a feasible solution after the true parameters are revealed, but at an additional cost. Second, we propose a corresponding algorithmic approach for our framework, which handles all packing and covering linear programs. Our approach is inspired by the prior work of Mandi and Guns, though with crucial modifications and re-derivations for our very different setting. Experimentation demonstrates the superior empirical performance of our method over classical approaches.

preprint2021arXiv

Uncertainty about Uncertainty: Optimal Adaptive Algorithms for Estimating Mixtures of Unknown Coins

Given a mixture between two populations of coins, "positive" coins that each have -- unknown and potentially different -- bias $\geq\frac{1}{2}+Δ$ and "negative" coins with bias $\leq\frac{1}{2}-Δ$ , we consider the task of estimating the fraction $ρ$ of positive coins to within additive error $ε$ . We achieve an upper and lower bound of $Θ(\fracρ{ε^2Δ^2}\log\frac{1}δ)$ samples for a $1-δ$ probability of success, where crucially, our lower bound applies to all fully-adaptive algorithms. Thus, our sample complexity bounds have tight dependence for every relevant problem parameter. A crucial component of our lower bound proof is a decomposition lemma (see Lemmas 17 and 18) showing how to assemble partially-adaptive bounds into a fully-adaptive bound, which may be of independent interest: though we invoke it for the special case of Bernoulli random variables (coins), it applies to general distributions. We present simulation results to demonstrate the practical efficacy of our approach for realistic problem parameters for crowdsourcing applications, focusing on the "rare events" regime where $ρ$ is small. The fine-grained adaptive flavor of both our algorithm and lower bound contrasts with much previous work in distributional testing and learning.

preprint2016arXiv

Optimizing Star-Convex Functions

We introduce a polynomial time algorithm for optimizing the class of star-convex functions, under no restrictions except boundedness on a region about the origin, and Lebesgue measurability. The algorithm's performance is polynomial in the requested number of digits of accuracy, contrasting with the previous best known algorithm of Nesterov and Polyak that has exponential dependence, and that further requires Lipschitz second differentiability of the function, but has milder dependence on the dimension of the domain. Star-convex functions constitute a rich class of functions generalizing convex functions to new parameter regimes, and which confound standard variants of gradient descent; more generally, we construct a family of star-convex functions where gradient-based algorithms provably give no information about the location of the global optimum. We introduce a new randomized algorithm for finding cutting planes based only on function evaluations, where, counterintuitively, the algorithm must look outside the feasible region to discover the structure of the star-convex function that lets it compute the next cut of the feasible region. We emphasize that the class of star-convex functions we consider is as unrestricted as possible: the class of Lebesgue measurable star-convex functions has theoretical appeal, introducing to the domain of polynomial-time algorithms a huge class with many interesting pathologies. We view our results as a step forward in understanding the scope of optimization techniques beyond the garden of convex optimization and local gradient-based methods.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Jasper C. H. Lee

Research overview

Is this your work?

5 publications

Branch & Learn for Recursively and Iteratively Solvable Problems in Predict+Optimize

Finite-Sample Maximum Likelihood Estimation of Location

Predict+Optimize for Packing and Covering LPs with Unknown Parameters in Constraints

Uncertainty about Uncertainty: Optimal Adaptive Algorithms for Estimating Mixtures of Unknown Coins

Optimizing Star-Convex Functions

See the researcher in context

Building this map preview