Author name cluster

Andrew Wan

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

2 author rows

SODA Conference 2015 Conference Paper

Approximate resilience, monotonicity, and the complexity of agnostic learning

Dana Dachman-Soled
Vitaly Feldman
Li-Yang Tan
Andrew Wan
Karl Wimmer

A function f is d -resilient if all its Fourier coefficients of degree at most d are zero, i. e. f is uncorrelated with all low-degree parities. We study the notion of approximate resilience of Boolean functions, where we say that f is α-approximately d -resilient if f is α-close to a [-1, 1]-valued d -resilient function in ℓ 1 distance. We show that approximate resilience essentially characterizes the complexity of agnostic learning of a concept class C over the uniform distribution. Roughly speaking, if all functions in a class C are far from being d -resilient then C can be learned agnostically in time n O ( d ) and conversely, if C contains a function close to being d -resilient then agnostic learning of C in the statistical query (SQ) framework of Kearns has complexity of at least n Ω( d ). Focusing on monotone Boolean functions, we exhibit the existence of near-optimal α-approximately -resilient monotone functions for all α > 0. Prior to our work, it was conceivable even that every monotone function is Ω(1)-far from any 1-resilient function. Furthermore, we construct simple, explicit monotone functions based on Tribes and CycleRun that are close to highly resilient functions. Our constructions are based on general resilience analysis and amplification techniques we introduce. These structural results, together with the characterization, imply nearly optimal lower bounds for agnostic learning of monotone juntas, a natural variant of the well-studied junta learning problem. In particular we show that no SQ algorithm can efficiently agnostically learn monotone k -juntas for any k = ω(1) and any constant error less than 1/2.

Details

FOCS Conference 2014 Conference Paper

Satisfiability and Evolution

Adi Livnat
Christos H. Papadimitriou
Aviad Rubinstein
Gregory Valiant
Andrew Wan

We show that, if truth assignments on n variables reproduce through recombination so that satisfaction of a particular Boolean function confers a small evolutionary advantage, then a polynomially large population over polynomially many generations (polynomial in n and the inverse of the initial satisfaction probability) will end up almost certainly consisting exclusively of satisfying truth assignments. We argue that this theorem sheds light on the problem of the evolution of complex adaptations.

Details

FOCS Conference 2011 Conference Paper

Pseudorandomness for Read-Once Formulas

Andrej Bogdanov
Periklis A. Papakonstantinou
Andrew Wan

We give an explicit construction of a pseudorandom generator for read-once formulas whose inputs can be read in arbitrary order. For formulas in n inputs and arbitrary gates of fan-in at most d = O(n/ log n), the pseudorandom generator uses (1 - Ω(1))n bits of randomness and produces an output that looks 2 -Ω(n) -pseudorandom to all such formulas. Our analysis is based on the following lemma. Let P = Mz+e, where M is the parity-check matrix of a sufficiently good binary error-correcting code of constant rate, z is a random string, e is a small-bias distribution, and all operations are modulo 2. Then for every pair of functions f, g: {0, 1} n/2 → {0, 1} and every equipartition (I, J) of [n], the distribution P is pseudorandom for the pair (f(x| I ), g(x| J )), where x| I and x| J denote the restriction of x to the coordinates in / and J, respectively. More generally, our result applies to read-once branching pro- grams of bounded width with arbitrary ordering of the inputs. We show that such branching programs are more powerful distinguishers than those that read their inputs in sequential order: There exist (explicit) pseudorandom distributions that separate these two types of branching programs.

Details

ICRA Conference 2010 Conference Paper

Superhuman performance of surgical tasks by robots using iterative learning from human-guided demonstrations

Jur van den Berg
Stephen Miller
Daniel Duckworth
Humphrey Hu
Andrew Wan
Xiao-Yu Fu
Ken Goldberg
Pieter Abbeel

In the future, robotic surgical assistants may assist surgeons by performing specific subtasks such as retraction and suturing to reduce surgeon tedium and reduce the duration of some operations. We propose an apprenticeship learning approach that has potential to allow robotic surgical assistants to autonomously execute specific trajectories with superhuman performance in terms of speed and smoothness. In the first step, we record a set of trajectories using human-guided backdriven motions of the robot. These are then analyzed to extract a smooth reference trajectory, which we execute at gradually increasing speeds using a variant of iterative learning control. We evaluate this approach on two representative tasks using the Berkeley Surgical Robots: a figure eight trajectory and a two handed knot-tie, a tedious suturing sub-task required in many surgical procedures. Results suggest that the approach enables (i) rapid learning of trajectories, (ii) smoother trajectories than the human-guided trajectories, and (iii) trajectories that are 7 to 10 times faster than the best human-guided trajectories.

Details

JMLR Journal 2007 Journal Article

Separating Models of Learning from Correlated and Uncorrelated Data

Ariel Elbaz
Homin K. Lee
Rocco A. Servedio
Andrew Wan

We consider a natural framework of learning from correlated data, in which successive examples used for learning are generated according to a random walk over the space of possible examples. A recent paper by Bshouty et al. (2003) shows that the class of polynomial-size DNF formulas is efficiently learnable in this random walk model; this result suggests that the Random Walk model is more powerful than comparable standard models of learning from independent examples, in which similarly efficient DNF learning algorithms are not known. We give strong evidence that the Random Walk model is indeed more powerful than the standard model, by showing that if any cryptographic one-way function exists (a universally held belief in cryptography), then there is a class of functions that can be learned efficiently in the Random Walk setting but not in the standard setting where all examples are independent. [abs] [ pdf ][ bib ] &copy JMLR 2007. ( edit, beta )

PDF Details

FOCS Conference 2007 Conference Paper

Testing for Concise Representations

Ilias Diakonikolas
Homin K. Lee
Kevin Matulef
Krzysztof Onak
Ronitt Rubinfeld
Rocco A. Servedio
Andrew Wan

We describe a general method for testing whether a function on n input variables has a concise representation. The approach combines ideas from the junta test of Fischer et al. 16 with ideas from learning theory, and yields property testers that make po! y(s/epsiv) queries (independent of n) for Boolean function classes such as s-term DNF formulas (answering a question posed by Parnas et al. [12]), sizes. decision trees, sizes Boolean formulas, and sizes Boolean circuits. The method can be applied to non-Boolean valued function classes as well. This is achieved via a generalization of the notion of van at ion/row Fischer et al. to non-Boolean functions. Using this generalization we extend the original junta test of Fischer et al. to work for non-Boolean functions, and give poly(s/e)-query testing algorithms for non-Boolean valued function classes such as sizes algebraic circuits and s-sparse polynomials over finite fields. We also prove an Omega(radic(s)) query lower bound for nonadaptively testing s-sparse polynomials over finite fields of constant size. This shows that in some instances, our general method yields a property tester with query complexity that is optimal (for nonadaptive algorithms) up to a polynomial factor.

Details