Author name cluster

Jane Lange

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.

16 papers

2 author rows

SODA Conference 2025 Conference Paper

Local Lipschitz Filters for Bounded-Range Functions with Applications to Arbitrary Real-Valued Functions

Jane Lange
Ephraim Linder
Sofya Raskhodnikova
Arsen Vasilyan

We study local filters for the Lipschitz property of real-valued functions f: V → [0, r ], where the Lipschitz property is defined with respect to an arbitrary undirected graph G = ( V, E ). We give nearly optimal local Lipschitz filters both with respect to ℓ 1 -distance and ℓ 0 -distance. Previous work only considered unbounded- range functions over [ n ] d. Jha and Raskhodnikova (SICOMP ‘13) gave an algorithm for such functions with lookup complexity exponential in d, which Awasthi et al. (ACM Trans. Comput. Theory) showed was necessary in this setting. We demonstrate that important applications of local Lipschitz filters can be accomplished with filters for functions whose range is bounded in [0, r ]. For functions f: [ n ] d → [0, r ], we achieve running time ( d r log n ) O (log r ) for the ℓ 1 -respecting filter and d O(r) polylog n for the ℓ 0 -respecting filter, thus circumventing the lower bound. Our local filters provide a novel Lipschitz extension that can be implemented locally. Furthermore, we show that our algorithms are nearly optimal in terms of the dependence on r for the domain {0, 1} d, an important special case of the domain [ n ] d. In addition, our lower bound resolves an open question of Awasthi et al. , removing one of the conditions necessary for their lower bound for general range. We prove our lower bound via a reduction from distribution-free Lipschitz testing and a new technique for proving hardness for adaptive algorithms. Finally, we provide two applications of our local filters to real-valued functions, with no restrictions on the range. In the first application, we use them in conjunction with the Laplace mechanism for differential privacy and noisy binary search to provide mechanisms for privately releasing outputs of black-box functions, even in the presence of malicious clients. In particular, our differentially private mechanism for arbitrary real-valued functions runs in time 2 polylog min( r, nd ) and, for honest clients, has accuracy comparable to the Laplace mechanism for Lipschitz functions, up to a factor of O (log min( r, nd )). In the second application, we use our local filters to obtain the first nontrivial tolerant tester for the Lipschitz property. Our tester works for functions of the form f: {0, 1} d → ℝ, makes queries, and has tolerance ratio 2. 01. Our applications demonstrate that local filters for bounded-range functions can be applied to construct efficient algorithms for arbitrary real-valued functions.

Details

NeurIPS Conference 2025 Conference Paper

Robust learning of halfspaces under log-concave marginals

Jane Lange
Arsen Vasilyan

We say that a classifier is $\text{\emph{adversarially robust}}$ to perturbations of norm $r$ if, with high probability over a point $x$ drawn from the input distribution, there is no point within distance $\le r$ from $x$ that is classified differently. The $\text{\emph{boundary volume}}$ is the probability that a point falls within distance $r$ of a point with a different label. This work studies the task of learning a hypothesis with small boundary volume, where the input is distributed as a subgaussian isotropic log-concave distribution over $\mathbb{R}^d$. Linear threshold functions are adversarially robust; they have boundary volume proportional to $r$. Such concept classes are efficiently learnable by polynomial regression, which produces a polynomial threshold function (PTF), but PTFs in general may have boundary volume $\Omega(1)$, even for $r \ll 1$. We give an algorithm that agnostically learns linear threshold functions and returns a classfier with boundary volume $O(r+\varepsilon)$ at radius of perturbation $r$. The time and sample complexity of $d^{\tilde{O}(1/\varepsilon^2)}$ matches the complexity of polynomial regression. Our algorithm augments the classic approach of polynomial regression with three additional steps: \ $\quad$ a) performing the $\ell_1$-error regression under $\ell_1$ noise sensitivity constraints, \ $\quad$ b) a structured partitioning and rounding step that returns a Boolean classifier with error $\mathrm{opt} + O(\varepsilon)$ and noise sensitivity $O(r+\varepsilon)$ simultaneously, and \ $\quad c)$ a local corrector that ``smooths'' a function with low noise sensitivity into a function that is adversarially robust.

PDF Details

FOCS Conference 2023 Conference Paper

Agnostic proper learning of monotone functions: beyond the black-box correction barrier

Jane Lange
Arsen Vasilyan

We give the first agnostic, efficient, proper learning algorithm for monotone Boolean functions. Given $2^{\tilde{O}(\sqrt{n} / \varepsilon)}$ uniformly random examples of an unknown function $f: \{ \pm 1\}^{n} \rightarrow\{ \pm 1\}$, our algorithm outputs a hypothesis $g: \{ \pm 1\}^{n} \rightarrow\{ \pm 1\}$ that is monotone and (opt $+\varepsilon$)-close to f, where opt is the distance from f to the closest monotone function. The running time of the algorithm (and consequently the size and evaluation time of the hypothesis) is also $2^{\tilde{O}(\sqrt{n} / \varepsilon)}$, nearly matching the lower bound of [13]. We also give an algorithm for estimating up to additive error $\varepsilon$ the distance of an unknown function f to monotone using a run-time of $2^{\tilde{O}(\sqrt{n} / \varepsilon)}$. Previously, for both of these problems, sample-efficient algorithms were known, but these algorithms were not run-time efficient. Our work thus closes this gap in our knowledge between the run-time and sample complexity. This work builds upon the improper learning algorithm of [17] and the proper semiagnostic learning algorithm of [40], which obtains a non-monotone Boolean-valued hypothesis, then “corrects” it to monotone using query-efficient local computation algorithms on graphs. This black-box correction approach can achieve no error better than 2 opt $+\varepsilon$ information-theoretically; we bypass this barrier bya)augmenting the improper learner with a convex optimization step, andb)learning and correcting a real-valued function before rounding its values to Boolean. Our real-valued correction algorithm solves the “poset sorting” problem of [40] for functions over general posets with non-Boolean labels.

Details

NeurIPS Conference 2023 Conference Paper

Harnessing the power of choices in decision tree learning

Guy Blanc
Jane Lange
Chirag Pabbaraju
Colin Sullivan
Li-Yang Tan
Mo Tiwari

We propose a simple generalization of standard and empirically successful decision tree learning algorithms such as ID3, C4. 5, and CART. These algorithms, which have been central to machine learning for decades, are greedy in nature: they grow a decision tree by iteratively splitting on the best attribute. Our algorithm, Top-$k$, considers the $k$ best attributes as possible splits instead of just the single best attribute. We demonstrate, theoretically and empirically, the power of this simple generalization. We first prove a greediness hierarchy theorem showing that for every $k\in \mathbb{N}$, Top-$(k+1)$ can be dramatically more powerful than Top-$k$: there are data distributions for which the former achieves accuracy $1-\epsilon$, whereas the latter only achieves accuracy $\frac{1}{2}+\epsilon$. We then show, through extensive experiments, that Top-$k$ outperforms the two main approaches to decision tree learning: classic greedy algorithms and more recent ``optimal decision tree'' algorithms. On one hand, Top-$k$ consistently enjoys significant accuracy gains over greedy algorithms across a wide range of benchmarks. On the other hand, Top-$k$ is markedly more scalable than optimal decision tree algorithms and is able to handle dataset and feature set sizes that remain far beyond the reach of these algorithms. The code to reproduce our results is available at https: //github. com/SullivanC19/pydl8. 5-topk.

PDF Details

STOC Conference 2023 Conference Paper

Lifting Uniform Learners via Distributional Decomposition

Guy Blanc
Jane Lange
Ali Malik
Li-Yang Tan

We show how any PAC learning algorithm that works under the uniform distribution can be transformed, in a blackbox fashion, into one that works under an arbitrary and unknown distribution ‍ D . The efficiency of our transformation scales with the inherent complexity of ‍ D , running in ( n , ( md ) d ) time for distributions over n whose pmfs are computed by depth- d decision trees, where m is the sample complexity of the original algorithm. For monotone distributions our transformation uses only samples from ‍ D , and for general ones it uses subcube conditioning samples. A key technical ingredient is an algorithm which, given the aforementioned access to D , produces an optimal decision tree decomposition of D : an approximation of D as a mixture of uniform distributions over disjoint subcubes. With this decomposition in hand, we run the uniform-distribution learner on each subcube and combine the hypotheses using the decision tree. This algorithmic decomposition lemma also yields new algorithms for learning decision tree distributions with runtimes that exponentially improve on the prior state of the art—results of independent interest in distribution learning.

Details

ICML Conference 2022 Conference Paper

A query-optimal algorithm for finding counterfactuals

Guy Blanc
Caleb Koch 0001
Jane Lange
Li-Yang Tan

We design an algorithm for finding counterfactuals with strong theoretical guarantees on its performance. For any monotone model $f: X^d \to \{0, 1\}$ and instance $x^\star$, our algorithm makes \[{S}(f)^{O(\Delta_f(x^\star))}\cdot \log d\]{queries} to $f$ and returns an {\sl optimal} counterfactual for $x^\star$: a nearest instance $x’$ to $x^\star$ for which $f(x’)\ne f(x^\star)$. Here $S(f)$ is the sensitivity of $f$, a discrete analogue of the Lipschitz constant, and $\Delta_f(x^\star)$ is the distance from $x^\star$ to its nearest counterfactuals. The previous best known query complexity was $d^{\, O(\Delta_f(x^\star))}$, achievable by brute-force local search. We further prove a lower bound of $S(f)^{\Omega(\Delta_f(x^\star))} + \Omega(\log d)$ on the query complexity of any algorithm, thereby showing that the guarantees of our algorithm are essentially optimal.

Details

ICML Conference 2022 Conference Paper

Popular decision tree algorithms are provably noise tolerant

Guy Blanc
Jane Lange
Ali Malik
Li-Yang Tan

Using the framework of boosting, we prove that all impurity-based decision tree learning algorithms, including the classic ID3, C4. 5, and CART, are highly noise tolerant. Our guarantees hold under the strongest noise model of nasty noise, and we provide near-matching upper and lower bounds on the allowable noise rate. We further show that these algorithms, which are simple and have long been central to everyday machine learning, enjoy provable guarantees in the noisy setting that are unmatched by existing algorithms in the theoretical literature on decision tree learning. Taken together, our results add to an ongoing line of research that seeks to place the empirical success of these practical decision tree algorithms on firm theoretical footing.

Details

FOCS Conference 2022 Conference Paper

Properly learning monotone functions via local correction

Jane Lange
Ronitt Rubinfeld
Arsen Vasilyan

We give a $2^{\tilde{O}(\sqrt{n}/\varepsilon)}$-time algorithm for properly learning monotone Boolean functions under the uniform distribution over $\{0, 1\}^{n}$. Our algorithm is robust to adversarial label noise and has a running time nearly matching that of the state-of-the-art improper learning algorithm of Bshouty and Tamon (JACM 96) and an information-theoretic lower bound of Blais et al (RANDOM ’15). Prior to this work, no proper learning algorithm with running time smaller than $2^{\Omega(n)}$ was known to exist. The core of our proper learner is a local computation algorithm for sorting binary labels on a poset. Our algorithm is built on a body of work on distributed greedy graph algorithms; specifically we rely on a recent work of Ghaffari (FOCS’22), which gives an efficient algorithm for computing maximal matchings in a graph in the LCA model of Rubinfeld et al and Alon et al (ICS’II, SODA’12). The applications of our local sorting algorithm extend beyond learning on the Boolean cube: we also give a tolerant tester for Boolean functions over general posets that distinguishes functions that are $\varepsilon$/3-close to monotone from those that are $\varepsilon-$far. Previous tolerant testers for the Boolean cube only distinguished between $\varepsilon/\Omega(\sqrt{n}$)-close and $\varepsilon-$far.

Details

STOC Conference 2022 Conference Paper

The query complexity of certification

Guy Blanc
Caleb Koch 0001
Jane Lange
Li-Yang Tan

We study the problem of certification: given queries to a function f : {0,1} n → {0,1} with certificate complexity ≤ k and an input x ⋆ , output a size- k certificate for f ’s value on x ⋆ . For monotone functions, a classic local search algorithm of Angluin accomplishes this task with n queries, which we show is optimal for local search algorithms. Our main result is a new algorithm for certifying monotone functions with O ( k 8 log n ) queries, which comes close to matching the information-theoretic lower bound of Ω( k log n ). The design and analysis of our algorithm are based on a new connection to threshold phenomena in monotone functions. We further prove exponential-in- k lower bounds when f is non-monotone, and when f is monotone but the algorithm is only given random examples of f . These lower bounds show that assumptions on the structure of f and query access to it are both necessary for the polynomial dependence on k that we achieve.

Details

IJCAI Conference 2021 Conference Paper

Politeness for the Theory of Algebraic Datatypes (Extended Abstract)

Ying Sheng
Yoni Zohar
Christophe Ringeissen
Jane Lange
Pascal Fontaine
Clark Barrett

Algebraic datatypes, and among them lists and trees, have attracted a lot of interest in automated reasoning and Satisfiability Modulo Theories (SMT). Since its latest stable version, the SMT-LIB standard defines a theory of algebraic datatypes, which is currently supported by several mainstream SMT solvers. In this paper, we study this particular theory of datatypes and prove that it is strongly polite, showing also how it can be combined with other arbitrary disjoint theories using polite combination. Our results cover both inductive and finite datatypes, as well as their union. The combination method uses a new, simple, and natural notion of additivity, that enables deducing strong politeness from (weak) politeness.

PDF Details DOI

FOCS Conference 2021 Conference Paper

Properly learning decision trees in almost polynomial time

Guy Blanc
Jane Lange
Mingda Qiao
Li-Yang Tan

We give an $n^{O(\log\log n)}$ -time membership query algorithm for properly and agnostically learning decision trees under the uniform distribution over $\{\pm 1\}^{n}$. Even in the realizable setting, the previous fastest runtime was $n^{O(\log n)}$, a consequence of a classic algorithm of Ehrenfeucht and Haussler. Our algorithm shares similarities with practical heuristics for learning decision trees, which we augment with additional ideas to circumvent known lower bounds against these heuristics. To analyze our algorithm, we prove a new structural result for decision trees that strengthens a theorem of O'Donnell, Saks, Schramm, and Servedio. While the OSSS theorem says that every decision tree has an influential variable, we show how every decision tree can be “pruned” so that every variable in the resulting tree is influential.

Details

NeurIPS Conference 2021 Conference Paper

Provably efficient, succinct, and precise explanations

Guy Blanc
Jane Lange
Li-Yang Tan

We consider the problem of explaining the predictions of an arbitrary blackbox model $f$: given query access to $f$ and an instance $x$, output a small set of $x$'s features that in conjunction essentially determines $f(x)$. We design an efficient algorithm with provable guarantees on the succinctness and precision of the explanations that it returns. Prior algorithms were either efficient but lacked such guarantees, or achieved such guarantees but were inefficient. We obtain our algorithm via a connection to the problem of {\sl implicitly} learning decision trees. The implicit nature of this learning task allows for efficient algorithms even when the complexity of~$f$ necessitates an intractably large surrogate decision tree. We solve the implicit learning problem by bringing together techniques from learning theory, local computation algorithms, and complexity theory. Our approach of “explaining by implicit learning” shares elements of two previously disparate methods for post-hoc explanations, global and local explanations, and we make the case that it enjoys advantages of both.

PDF Details

SODA Conference 2021 Conference Paper

Query strategies for priced information, revisited

Guy Blanc
Jane Lange
Li-Yang Tan

We consider the problem of designing query strategies for priced information, introduced by Charikar et al. In this problem the algorithm designer is given a function f: {0, 1} n → {±1} and a price associated with each of the n coordinates. The goal is to design a query strategy for determining f 's value on unknown inputs for minimum cost. Prior works on this problem have focused on specific classes of functions. We analyze a simple and natural strategy that applies to all functions f, and show that its performance relative to the optimal strategy can be expressed in terms of a basic complexity measure of f, its influence. For ∊ ∊ (0, ½), writing opt to denote the expected cost of the optimal strategy that errs on at most an ∊ -fraction of inputs, our strategy has expected cost opt · Inf( f )/ ∊ 2 and also errs on at most an O(∊) -fraction of inputs. This connection yields new guarantees that complement existing ones for a number of function classes that have been studied in this context, as well as new guarantees for new classes. Finally, we show that improving on the parameters that we achieve will require making progress on the longstanding open problem of properly learning decision trees.

Details

NeurIPS Conference 2020 Conference Paper

Estimating decision tree learnability with polylogarithmic sample complexity

Guy Blanc
Neha Gupta
Jane Lange
Li-Yang Tan

We show that top-down decision tree learning heuristics (such as ID3, C4. 5, and CART) are amenable to highly efficient {\sl learnability estimation}: for monotone target functions, the error of the decision tree hypothesis constructed by these heuristics can be estimated with {\sl polylogarithmically} many labeled examples, exponentially smaller than the number necessary to run these heuristics, and indeed, exponentially smaller than information-theoretic minimum required to learn a good decision tree. This adds to a small but growing list of fundamental learning algorithms that have been shown to be amenable to learnability estimation. En route to this result, we design and analyze sample-efficient {\sl minibatch} versions of top-down decision tree learning heuristics and show that they achieve the same provable guarantees as the full-batch versions. We further give ``active local'' versions of these heuristics: given a test point $x^\star$, we show how the label $T(x^\star)$ of the decision tree hypothesis $T$ can be computed with polylogarithmically many labeled examples, exponentially smaller than the number necessary to learn~$T$.

PDF Details

ICML Conference 2020 Conference Paper

Provable guarantees for decision tree induction: the agnostic setting

Guy Blanc
Jane Lange
Li-Yang Tan

We give strengthened provable guarantees on the performance of widely employed and empirically successful {\sl top-down decision tree learning heuristics}. While prior works have focused on the realizable setting, we consider the more realistic and challenging {\sl agnostic} setting. We show that for all monotone functions $f$ and $s\in \mathbb{N}$, these heuristics construct a decision tree of size $s^{\tilde{O}((\log s)/\varepsilon^2)}$ that achieves error $\le \mathsf{opt}_s + \varepsilon$, where $\mathsf{opt}_s$ denotes the error of the optimal size-$s$ decision tree for $f$. Previously such a guarantee was not known to be achievable by any algorithm, even one that is not based on top-down heuristics. We complement our algorithmic guarantee with a near-matching $s^{\tilde{\Omega}(\log s)}$ lower bound.

Details

NeurIPS Conference 2020 Conference Paper

Universal guarantees for decision tree induction via a higher-order splitting criterion

Guy Blanc
Neha Gupta
Jane Lange
Li-Yang Tan

We propose a simple extension of {\sl top-down decision tree learning heuristics} such as ID3, C4. 5, and CART. Our algorithm achieves provable guarantees for all target functions $f: \{-1, 1\}^n \to \{-1, 1\}$ with respect to the uniform distribution, circumventing impossibility results showing that existing heuristics fare poorly even for simple target functions. The crux of our extension is a new splitting criterion that takes into account the correlations between $f$ and {\sl small subsets} of its attributes. The splitting criteria of existing heuristics (e. g. Gini impurity and information gain), in contrast, are based solely on the correlations between $f$ and its {\sl individual} attributes. Our algorithm satisfies the following guarantee: for all target functions $f: \{-1, 1\}^n \to \{-1, 1\}$, sizes $s\in \N$, and error parameters $\eps$, it constructs a decision tree of size $s^{\tilde{O}((\log s)^2/\eps^2)}$ that achieves error $\le O(\opt_s) + \eps$, where $\opt_s$ denotes the error of the optimal size-$s$ decision tree for $f$. A key technical notion that drives our analysis is the {\sl noise stability} of $f$, a well-studied smoothness measure of $f$.

PDF Details