Arrow Research search

Author name cluster

Santosh S. Vempala

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.

75 papers
2 author rows

Possible papers

75

AAAI Conference 2025 Conference Paper

Does GPT Really Get It? A Hierarchical Scale to Quantify Human and AI’s Understanding of Algorithms

  • Mirabel Reid
  • Santosh S. Vempala

As Large Language Models (LLMs) are used for increasingly complex cognitive tasks, a natural question is whether AI really understands. The study of understanding in LLMs is in its infancy, and the community has yet to incorporate research and insights from philosophy, psychology, and education. Here we focus on understanding algorithms, and propose a hierarchy of levels of understanding. We validate the hierarchy using a study with human subjects (undergraduate and graduate students). Following this, we apply the hierarchy to large language models (generations of GPT), revealing interesting similarities and differences with humans. We expect that our rigorous criteria for algorithm understanding will help monitor and quantify AI's progress in such cognitive domains.

PDF Details DOI

FOCS Conference 2025 Conference Paper

Faster Logconcave Sampling from a Cold Start in High Dimension

  • Yunbum Kook
  • Santosh S. Vempala

We present a faster algorithm to generate a warm start for sampling an arbitrary logconcave density specified by an evaluation oracle, leading to the first sub-cubic sampling algorithms for inputs in (near-)isotropic position. A long line of prior work incurred a warm-start penalty of at least linear in the dimension, hitting a cubic barrier, even for the special case of uniform sampling from convex bodies. Our improvement relies on two key ingredients of independent interest. (1) We show how to sample given a warm start in weaker notions of distance, in particular q-Rényi divergence for $q=\widetilde{O}$ (1), whereas previous analyses required stringent $\infty$-Rényi divergence (with the exception of Hit-and-Run, whose known mixing time is higher). This marks the first improvement in the required warmness since Lovász and Simonovits (1991). (2) We refine and generalize the $\log$-Sobolev inequality of Lee and Vempala (2018), originally established for isotropic logconcave distributions in terms of the diameter of the support, to logconcave distributions in terms of a geometric average of the support diameter and the largest eigenvalue of the covariance matrix.

Details

STOC Conference 2025 Conference Paper

Sampling and Integration of Logconcave Functions by Algorithmic Diffusion

  • Yunbum Kook
  • Santosh S. Vempala

We study the complexity of sampling, rounding, and integrating arbitrary logconcave functions given an evaluation oracle. Our new approach provides the first complexity improvements in nearly two decades for general logconcave functions for all three problems, and matches the best-known complexities for the special case of uniform distributions on convex bodies. For the sampling problem, our output guarantees are significantly stronger than previously known, and lead to a streamlined analysis of statistical estimation based on dependent random samples.

Details

STOC Conference 2024 Conference Paper

Calibrated Language Models Must Hallucinate

  • Adam Tauman Kalai
  • Santosh S. Vempala

Recent language models generate false but plausible-sounding text with surprising frequency. Such “hallucinations” are an obstacle to the usability of language-based AI systems and can harm people who rely upon their outputs. This work shows that there is an inherent statistical lower-bound on the rate that pretrained language models hallucinate certain types of facts, having nothing to do with the transformer LM architecture or data quality. For “arbitrary” facts whose veracity cannot be determined from the training data, we show that hallucinations must occur at a certain rate for language models that satisfy a statistical calibration condition appropriate for generative language models. Specifically, if the maximum probability of any fact is bounded, we show that the probability of generating a hallucination is close to the fraction of facts that occur exactly once in the training data (a “Good-Turing” estimate), even assuming ideal training data without errors. One conclusion is that models pretrained to be sufficiently good predictors (i.e., calibrated) may require post-training to mitigate hallucinations on the type of arbitrary facts that tend to appear once in the training set. However, our analysis also suggests that there is no statistical reason that pretraining will lead to hallucination on facts that tend to appear more than once in the training data (like references to publications such as articles and books, whose hallucinations have been particularly notable and problematic) or on systematic facts (like arithmetic calculations). Therefore, different architectures and learning algorithms may mitigate these latter types of hallucinations.

Details

NeurIPS Conference 2024 Conference Paper

In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies

  • Yunbum Kook
  • Santosh S. Vempala
  • Matthew S. Zhang

We present a new random walk for uniformly sampling high-dimensional convex bodies. It achieves state-of-the-art runtime complexity with stronger guarantees on the output than previously known, namely in Rényi divergence (which implies TV, $\mathcal{W}_2$, KL, $\chi^2$). The proof departs from known approaches for polytime algorithms for the problem - we utilize a stochastic diffusion perspective to show contraction to the target distribution with the rate of convergence determined by functional isoperimetric constants of the stationary density.

PDF Details DOI

FOCS Conference 2023 Conference Paper

Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error

  • He Jia
  • Pravesh K. Kothari
  • Santosh S. Vempala

We present a polynomial-time algorithm for robustly learning an unknown affine transformation of the standard hypercube from samples, an important and well-studied setting for independent component analysis (ICA). Specifically, given an $\varepsilon$-corrupted sample from a distribution D obtained by applying an unknown affine transformation $x \rightarrow A x+b$ to the uniform distribution on a d-dimensional hypercube $[-1, 1]^{d}$, our algorithm constructs $\widehat{A}, \hat{b}$ such that the total variation distance of the distribution $\widehat{D}$ from D is $O(\varepsilon)$ using poly $(d)$ time and samples. Total variation distance is the information-theoretically strongest possible notion of distance in our setting and our recovery guarantees in this distance are optimal up to the absolute constant factor multiplying $\varepsilon$. In particular, if the rows of A are normalized to be unit length, our total variation distance guarantee implies a bound on the sum of the $\ell_{2}$ distances between the row vectors of A and $A^{\prime}, \sum_{i=1}^{d}\left\|a_{(i)}-\hat{a}_{(i)}\right\|_{2}=O(\varepsilon)$. In contrast, the strongest known prior results only yield an $\varepsilon^{O(1)}$ (relative) bound on the distance between individual $a_{i}$’s and their estimates and translate into an $O\left(d \varepsilon^{O(1)}\right)$ bound on the total variation distance. Prior algorithms for this problem rely on implementing standard approaches [12] for ICA based on the classical method of moments [18], [32] combined with robust moment estimators. We prove that any approach that relies on method of moments must provably fail to obtain a dimension independent bound on the total error $\sum_{i}\left\|a_{(i)}-\hat{a}_{(i)}\right\|_{2}$ (and consequently, also in total variation distance). Our key innovation is a new approach to ICA (even to outlier-free ICA) that circumvents the difficulties in the classical method of moments and instead relies on a new geometric certificate of correctness of an affine transformation. Our algorithm, Robust Gradient Descent, is based on a new method that iteratively improves its estimate of the unknown affine transformation whenever the requirements of the certificate are not met.

Details

FOCS Conference 2023 Conference Paper

The Bit Complexity of Efficient Continuous Optimization

  • Mehrdad Ghadiri
  • Richard Peng
  • Santosh S. Vempala

We analyze the bit complexity of efficient algorithms for fundamental optimization problems, such as linear regression, p-norm regression, and linear programming (LP). State-of-the-art algorithms are iterative, and in terms of the number of arithmetic operations, they match the current time complexity of multiplying two n-by-n matrices (up to polylogarithmic factors). However, previous work has typically assumed infinite precision arithmetic, and due to complicated inverse maintenance techniques, the actual running times of these algorithms are unknown. To settle the running time and bit complexity of these algorithms, we demonstrate that a core common subroutine, known as inverse maintenance, is backward-stable. Additionally, we show that iterative approaches for solving constrained weighted regression problems can be accomplished with bounded-error preconditioners. Specifically, we prove that linear programs can be solved approximately in matrix multiplication time multiplied by polylog factors that depend on the condition number $\kappa$ of the matrix and the inner and outer radius of the LP problem. p-norm regression can be solved approximately in matrix multiplication time multiplied by polylog factors in $\kappa$. Lastly, linear regression can be solved approximately in input-sparsity time multiplied by polylog factors in $\kappa$. Furthermore, we present results for achieving lower than matrix multiplication time for p-norm regression by utilizing faster solvers for sparse linear systems.

Details

STOC Conference 2022 Conference Paper

Robustly learning mixtures of k arbitrary Gaussians

  • Ainesh Bakshi
  • Ilias Diakonikolas
  • He Jia
  • Daniel M. Kane
  • Pravesh K. Kothari
  • Santosh S. Vempala

We give a polynomial-time algorithm for the problem of robustly estimating a mixture of k arbitrary Gaussians in ℝ d , for any fixed k , in the presence of a constant fraction of arbitrary corruptions. This resolves the main open problem in several previous works on algorithmic robust statistics, which addressed the special cases of robustly estimating (a) a single Gaussian, (b) a mixture of TV-distance separated Gaussians, and (c) a uniform mixture of two Gaussians. Our main tools are an efficient partial clustering algorithm that relies on the sum-of-squares method, and a novel tensor decomposition algorithm that allows errors in both Frobenius norm and low-rank terms.

Details

STOC Conference 2021 Conference Paper

Reducing isotropy and volume to KLS: an o *( n 3 ψ 2 ) volume algorithm

  • He Jia
  • Aditi Laddha
  • Yin Tat Lee
  • Santosh S. Vempala

We show that the volume of a convex body in R n in the general membership oracle model can be computed to within relative error ε using O ( n 3 ψ 2 /ε 2 ) oracle queries, where ψ is the KLS constant. With the current bound of ψ= O ( n o (1) ), this gives an O ( n 3+ o (1) /ε 2 ) algorithm, the first improvement on the Lovász-Vempala O ( n 4 /ε 2 ) algorithm from 2003. The main new ingredient is an O ( n 3 ψ 2 ) algorithm for isotropic transformation, following which we can apply the O ( n 3 /ε 2 ) volume algorithm of Cousins and Vempala for well-rounded convex bodies. A positive resolution of the KLS conjecture would imply an O ( n 3 /є 2 ) volume algorithm. We also give an efficient implementation of the new algorithm for convex polytopes defined by m inequalities in R n : polytope volume can be estimated in time O ( mn c /ε 2 ) where c <3.2 depends on the current matrix multiplication exponent and improves on the previous best bound.

Details

SODA Conference 2021 Conference Paper

Solving Sparse Linear Systems Faster than Matrix Multiplication

  • Richard Peng
  • Santosh S. Vempala

Can linear systems be solved faster than matrix multiplication? While there has been remarkable progress for the special cases of graph structured linear systems, in the general setting, the bit complexity of solving an n × n linear system Ax = b is Õ ( n ω ), where ω < 2. 372864 is the matrix multiplication exponent. Improving on this has been an open problem even for sparse linear systems with poly( n ) condition number. In this paper, we present an algorithm that solves linear systems in sparse matrices asymptotically faster than matrix multiplication for any ω > 2. This speedup holds for any input matrix A with o ( n ω –1 /log( κ ( A ))) non-zeros, where κ ( A ) is the condition number of A. For poly( n )-conditioned matrices with Õ ( n ) nonzeros, and the current value of ω, the bit complexity of our algorithm to solve to within any 1/poly( n ) error is O ( n 2. 331645 ). Our algorithm can be viewed as an efficient, randomized implementation of the block Krylov method via recursive low displacement rank factorizations. It is inspired by the algorithm of [Eberly et al. ISSAC ‘06 ‘07] for inverting matrices over finite fields. In our analysis of numerical stability, we develop matrix anti-concentration techniques to bound the smallest eigenvalue and the smallest gap in eigenvalues of semi-random matrices.

Details

STOC Conference 2020 Conference Paper

Strong self-concordance and sampling

  • Aditi Laddha
  • Yin Tat Lee
  • Santosh S. Vempala

Motivated by the Dikin walk, we develop aspects of the interior-point theory for sampling in high dimension. Specifically, we introduce the notions of strong self-concordance and symmetry for a barrier. These properties imply that the Dikin walk defined using a strongly self-concordant barrier with symmetry parameter ν mixes in Õ( n ν) steps from a warm start for a convex body in ℝ n . For many natural barriers, ν is roughly bounded by ν, the standard self-concordance parameter. We also show that these properties hold for the Lee-Sidford barrier. As a consequence, we obtain the first walk that mixes in Õ( n 2 ) steps for an arbitrary polytope in ℝ n . Strong self-concordance for other barriers leads to an interesting (and unexpected) connection — for the universal and entropic barriers, it is implied by the KLS conjecture.

Details

STOC Conference 2018 Conference Paper

Convergence rate of riemannian Hamiltonian Monte Carlo and faster polytope volume computation

  • Yin Tat Lee
  • Santosh S. Vempala

We give the first rigorous proof of the convergence of Riemannian Hamiltonian Monte Carlo, a general (and practical) method for sampling Gibbs distributions. Our analysis shows that the rate of convergence is bounded in terms of natural smoothness parameters of an associated Riemannian manifold. We then apply the method with the manifold defined by the log barrier function to the problems of (1) uniformly sampling a polytope and (2) computing its volume, the latter by extending Gaussian cooling to the manifold setting. In both cases, the total number of steps needed is O * ( mn 2/3 ), improving the state of the art. A key ingredient of our analysis is a proof of an analog of the KLS conjecture for Gibbs distributions over manifolds.

Details

STOC Conference 2018 Conference Paper

Stochastic localization + Stieltjes barrier = tight bound for log-Sobolev

  • Yin Tat Lee
  • Santosh S. Vempala

Logarithmic Sobolev inequalities are a powerful way to estimate the rate of convergence of Markov chains and to derive concentration inequalities on distributions. We prove that the log-Sobolev constant of any isotropic logconcave density in R n with support of diameter D is Ω(1/ D ), resolving a question posed by Frieze and Kannan in 1997. This is asymptotically the best possible estimate and improves on the previous bound of Ω(1/ D 2 ) by Kannan-Lovász-Montenegro. It follows that for any isotropic logconcave density, the ball walk with step size δ=Θ(1/√ n ) mixes in O * ( n 2 D ) proper steps from any starting point. This improves on the previous best bound of O * ( n 2 D 2 ) and is also asymptotically tight. The new bound leads to the following refined large deviation inequality for an L -Lipschitz function g over an isotropic logconcave density p : for any t >0, [complex formula not displayed] where ḡ is the median or mean of g for x ∼ p ; this improves on previous bounds by Paouris and by Guedon-Milman. Our main proof is based on stochastic localization together with a Stieltjes-type barrier function.

Details

FOCS Conference 2017 Conference Paper

Eldan's Stochastic Localization and the KLS Hyperplane Conjecture: An Improved Lower Bound for Expansion

  • Yin Tat Lee
  • Santosh S. Vempala

We show that the KLS constant for n-dimensional isotropic logconcavemeasures is O(n^{1/4}), improving on the current best bound ofO(n^{1/3}√{\log n}). As corollaries we obtain the same improvedbound on the thin-shell estimate, Poincar\e constant and Lipschitzconcentration constant and an alternative proof of this bound forthe isotropic constant; it also follows that the ball walk for samplingfrom an isotropic logconcave density in \R^{n} converges in O^{*}(n^{2. 5})steps from a warm start.

Details

STOC Conference 2017 Conference Paper

Geodesic walks in polytopes

  • Yin Tat Lee
  • Santosh S. Vempala

We introduce the geodesic walk for sampling Riemannian manifolds and apply it to the problem of generating uniform random points from the interior of polytopes in ℝ n specified by m inequalities. The walk is a discrete-time simulation of a stochastic differential equation (SDE) on the Riemannian manifold equipped with the metric induced by the Hessian of a convex function; each step is the solution of an ordinary differential equation (ODE). The resulting sampling algorithm for polytopes mixes in O*(mn 3/4 ) steps. This is the first walk that breaks the quadratic barrier for mixing in high dimension, improving on the previous best bound of O*(mn) by Kannan and Narayanan for the Dikin walk. We also show that each step of the geodesic walk (solving an ODE) can be implemented efficiently, thus improving the time complexity for sampling polytopes. Our analysis of the geodesic walk for general Hessian manifolds does not assume positive curvature and might be of independent interest.

Details

SODA Conference 2017 Conference Paper

Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization

  • Vitaly Feldman
  • Cristóbal Guzmán
  • Santosh S. Vempala

Stochastic convex optimization, where the objective is the expectation of a random convex function, is an important and widely used method with numerous applications in machine learning, statistics, operations research and other areas. We study the complexity of stochastic convex optimization given only statistical query (SQ) access to the objective function. We show that well-known and popular first-order iterative methods can be implemented using only statistical queries. For many cases of interest we derive nearly matching upper and lower bounds on the estimation (sample) complexity including linear optimization in the most general setting. We then present several consequences for machine learning, differential privacy and proving concrete lower bounds on the power of convex optimization based methods. The key ingredient of our work is SQ algorithms and lower bounds for estimating the mean vector of a distribution over vectors supported on a convex body in ℝ d. This natural problem has not been previously studied and we show that our solutions can be used to get substantially improved SQ versions of Perceptron and other online algorithms for learning halfspaces.

Details

FOCS Conference 2016 Conference Paper

Accelerated Newton Iteration for Roots of Black Box Polynomials

  • Anand Louis
  • Santosh S. Vempala

We study the problem of computing the largest root of a real rooted polynomial p(x) to within error 'z' given only black box access to it, i. e. , for any x, the algorithm can query an oracle for the value of p(x), but the algorithm is not allowed access to the coefficients of p(x). A folklore result for this problem is that the largest root of a polynomial can be computed in O(n log (1/z)) polynomial queries using the Newton iteration. We give a simple algorithm that queries the oracle at only O(log n log(1/z)) points, where n is the degree of the polynomial. Our algorithm is based on a novel approach for accelerating the Newton method by using higher derivatives.

Details

FOCS Conference 2016 Conference Paper

Agnostic Estimation of Mean and Covariance

  • Kevin A. Lai
  • Anup B. Rao
  • Santosh S. Vempala

We consider the problem of estimating the mean and covariance of a distribution from i. i. d. samples in the presence of a fraction of malicious noise. This is in contrast to much recent work where the noise itself is assumed to be from a distribution of known type. The agnostic problem includes many interesting special cases, e. g. , learning the parameters of a single Gaussian (or finding the best-fit Gaussian) when a fraction of data is adversarially corrupted, agnostically learning mixtures, agnostic ICA, etc. We present polynomial-time algorithms to estimate the mean and covariance with error guarantees in terms of information-theoretic lower bounds. As a corollary, we also obtain an agnostic algorithm for Singular Value Decomposition.

Details

STOC Conference 2015 Conference Paper

Bypassing KLS: Gaussian Cooling and an O^*(n3) Volume Algorithm

  • Benjamin Cousins
  • Santosh S. Vempala

We present an O*(n 3 ) randomized algorithm for estimating the volume of a well-rounded convex body given by a membership oracle, improving on the previous best complexity of O*(n 4 ). The new algorithmic ingredient is an accelerated cooling schedule where the rate of cooling increases with the temperature. Previously, the known approach for potentially achieving such complexity relied on a positive resolution of the KLS hyperplane conjecture, a central open problem in convex geometry.

Details

STOC Conference 2015 Conference Paper

On the Complexity of Random Satisfiability Problems with Planted Solutions

  • Vitaly Feldman
  • Will Perkins 0001
  • Santosh S. Vempala

The problem of identifying a planted assignment given a random k-SAT formula consistent with the assignment exhibits a large algorithmic gap: while the planted solution can always be identified given a formula with O(n log n) clauses, there are distributions over clauses for which the best known efficient algorithms require n k/2 clauses. We propose and study a unified model for planted k-SAT, which captures well-known special cases. An instance is described by a planted assignment σ and a distribution on clauses with k literals. We define its distribution complexity as the largest r for which the distribution is not r-wise independent (1 ≤ r ≤ k for any distribution with a planted assignment).

Details

STOC Conference 2013 Conference Paper

Statistical algorithms and a lower bound for detecting planted cliques

  • Vitaly Feldman
  • Elena Grigorescu
  • Lev Reyzin
  • Santosh S. Vempala
  • Ying Xiao 0003

We introduce a framework for proving lower bounds on computational problems over distributions, based on a class of algorithms called statistical algorithms . For such algorithms, access to the input distribution is limited to obtaining an estimate of the expectation of any given function on a sample drawn randomly from the input distribution, rather than directly accessing samples. Most natural algorithms of interest in theory and in practice, e.g., moments-based methods, local search, standard iterative methods for convex optimization, MCMC and simulated annealing, are statistical algorithms or have statistical counterparts. Our framework is inspired by and generalize the statistical query model in learning theory [34]. Our main application is a nearly optimal lower bound on the complexity of any statistical algorithm for detecting planted bipartite clique distributions (or planted dense subgraph distributions) when the planted clique has size O(n 1/2-δ ) for any constant δ > 0. Variants of these problems have been assumed to be hard to prove hardness for other problems and for cryptographic applications. Our lower bounds provide concrete evidence of hardness, thus supporting these assumptions.

Details

STOC Conference 2013 Conference Paper

The approximate rank of a matrix and its algorithmic applications: approximate rank

  • Noga Alon
  • Troy Lee
  • Adi Shraibman
  • Santosh S. Vempala

We study the ε-rank of a real matrix A, defined for any ε > 0 as the minimum rank over matrices that approximate every entry of A to within an additive ε. This parameter is connected to other notions of approximate rank and is motivated by problems from various topics including communication complexity, combinatorial optimization, game theory, computational geometry and learning theory. Here we give bounds on the ε-rank and use them for algorithmic applications. Our main algorithmic results are (a) polynomial-time additive approximation schemes for Nash equilibria for 2-player games when the payoff matrices are positive semidefinite or have logarithmic rank and (b) an additive PTAS for the densest subgraph problem for similar classes of weighted graphs. We use combinatorial, geometric and spectral techniques; our main new tool is an algorithm for efficiently covering a convex body with translates of another convex body.

Details

FOCS Conference 2013 Conference Paper

The Complexity of Approximating Vertex Expansion

  • Anand Louis
  • Prasad Raghavendra
  • Santosh S. Vempala

We study the complexity of approximating the vertex expansion of graphs G = (V, E), defined as Φ V def = minSCV n. |N(S)|/(|S||V\S). We give a simple polynomialtime algorithm for finding a subset with vertex expansion O(√(Φ V log d)) where d is the maximum degree of the graph. Our main result is an asymptotically matching lower bound: under the Small Set Expansion (SSE) hypothesis, it is hard to find a subset with expansion less than C(√(Φ V log d)) for an absolute constant C. In particular, this implies for all constant ε > 0, it is SSE-hard to distinguish whether the vertex expansion <; ε or at least an absolute constant. The analogous threshold for edge expansion is √Φ with no dependence on the degree (Here Φ denotes the optimal edge expansion). Thus our results suggest that vertex expansion is harder to approximate than edge expansion. In particular, while Cheeger's algorithm can certify constant edge expansion, it is SSE-hard to certify constant vertex expansion in graphs.

Details

SODA Conference 2012 Conference Paper

Deterministic construction of an approximate M-ellipsoid and its applications to derandomizing lattice algorithms

  • Daniel Dadush
  • Santosh S. Vempala

We give a deterministic O (log n ) n -time and space algorithm for the Shortest Vector Problem (SVP) of a lattice under any norm, improving on the previous best deterministic n O ( n ) -time algorithms for general norms. This approaches the 2 O ( n ) -time and space complexity of the randomized sieve based SVP algorithms (Arvind and Joglekar, FSTTCS 2008), first introduced by Ajtai, Kumar and Sivakumar (STOC 2001) for ℓ 2 -SVP, and the M-ellipsoid covering based SVP algorithm of Dadush et al. (FOCS 2011).

Details

STOC Conference 2012 Conference Paper

Many sparse cuts via higher eigenvalues

  • Anand Louis
  • Prasad Raghavendra
  • Prasad Tetali
  • Santosh S. Vempala

Cheeger's fundamental inequality states that any edge-weighted graph has a vertex subset S such that its expansion (a.k.a. conductance) is bounded as follows: [ φ(S) def= (w(S,bar{S}))/(min set(w(S), w(bar(S)))) ≤ √(2 λ 2 ) ] where w is the total edge weight of a subset or a cut and λ 2 is the second smallest eigenvalue of the normalized Laplacian of the graph. Here we prove the following natural generalization: for any integer k ∈ [n], there exist ck disjoint subsets S 1 , ..., S ck , such that [ max i φ(S i ) ≤ C √(λ k log k) ] where λ k is the kth smallest eigenvalue of the normalized Laplacian and c 0 are suitable absolute constants. Our proof is via a polynomial-time algorithm to find such subsets, consisting of a spectral projection and a randomized rounding. As a consequence, we get the same upper bound for the small set expansion problem, namely for any k, there is a subset S whose weight is at most a O(1/k) fraction of the total weight and φ(S) ≤ C √(λ k log k). Both results are the best possible up to constant factors. The underlying algorithmic problem, namely finding k subsets such that the maximum expansion is minimized, besides extending sparse cuts to more than one subset, appears to be a natural clustering problem in its own right.

Details

FOCS Conference 2012 Conference Paper

The Cutting Plane Method Is Polynomial for Perfect Matchings

  • Karthekeyan Chandrasekaran
  • László A. Végh
  • Santosh S. Vempala

The cutting plane approach to optimal matchings has been discussed by several authors over the past decades, and its rate of convergence has been an open question. We prove that the cutting plane approach using Edmonds' blossom inequalities converges in polynomial time for the minimum-cost perfect matching problem. Our main insight is an LP-based method to select cutting planes. This cut selection procedure leads to a sequence of intermediate linear programs with a linear number of constraints whose optima are half-integral and supported by a disjoint union of odd cycles and edges. This structural property of the optima is instrumental in finding violated blossom inequalities (cuts) in linear time. Moreover, the number of cycles in the support of the half-integral optima acts as a potential function to show efficient convergence to an integral solution.

Details

SODA Conference 2011 Conference Paper

Algorithms for Implicit Hitting Set Problems

  • Karthekeyan Chandrasekaran
  • Richard M. Karp
  • Erick Moreno-Centeno
  • Santosh S. Vempala

A hitting set for a collection of sets is a set that has a nonempty intersection with each set in the collection; the hitting set problem is to find a hitting set of minimum cardinality. Motivated by instances of the hitting set problem where the number of sets to be hit is large, we introduce the notion of implicit hitting set problems. In an implicit hitting set problem the collection of sets to be hit is typically too large to list explicitly; instead, an oracle is provided which, given a set H, either determines that H is a hitting set or returns a set that H does not hit. We show a number of examples of classic implicit hitting set problems, and give a generic algorithm for solving such problems optimally. The main contribution of this paper is to show that this framework is valuable in developing approximation algorithms. We illustrate this methodology by presenting a simple on-line algorithm for the minimum feedback vertex set problem on random graphs. In particular our algorithm gives a feedback vertex set of size n –(1/ p ) log np (1 − o (1)) with probability at least 3/4 for the random graph G n, p (the smallest feedback vertex set is of size n − (2/ p ) log np (1 + o (1))). We also consider a planted model for the feedback vertex set in directed random graphs. Here we show that a hitting set for a polynomial-sized subset of cycles is a hitting set for the planted random graph and this allows us to exactly recover the planted feedback vertex set.

Details

FOCS Conference 2011 Conference Paper

An FPTAS for #Knapsack and Related Counting Problems

  • Parikshit Gopalan
  • Adam R. Klivans
  • Raghu Meka
  • Daniel Stefankovic
  • Santosh S. Vempala
  • Eric Vigoda

Given $n$ elements with non-negative integer weights $w_1, .. ., w_n$ and an integer capacity $C$, we consider the counting version of the classic knapsack problem: find the number of distinct subsets whose weights add up to at most $C$. We give the first deterministic, fully polynomial-time approximation scheme (FPTAS) for estimating the number of solutions to any knapsack constraint (our estimate has relative error $1 \pm \epsilon$). Our algorithm is based on dynamic programming. Previously, randomized polynomial-time approximation schemes (FPRAS) were known first by Morris and Sinclair via Markov chain Monte Carlo techniques, and subsequently by Dyer via dynamic programming and rejection sampling. In addition, we present a new method for deterministic approximate counting using {\em read-once branching programs. } Our approach yields an FPTAS for several other counting problems, including counting solutions for the multidimensional knapsack problem with a constant number of constraints, the general integer knapsack problem, and the contingency tables problem with a constant number of rows.

Details

FOCS Conference 2011 Conference Paper

Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings

  • Daniel Dadush
  • Chris Peikert
  • Santosh S. Vempala

We give a novel algorithm for enumerating lattice points in any convex body, and give applications to several classic lattice problems, including the Shortest and Closest Vector Problems (SVP and CVP, respectively) and Integer Programming (IP). Our enumeration technique relies on a classical concept from asymptotic convex geometry known as the M-ellipsoid, and uses as a crucial subroutine the recent algorithm of Micciancio and Voulgaris (STOC 2010)for lattice problems in the ℓ 2 norm. As a main technical contribution, which may be of independent interest, we build on the techniques of Klartag (Geometric and Functional Analysis, 2006) to give an expected 2 O(n) -time algorithm for computing an M-ellipsoid for any n-dimensional convex body. As applications, we give deterministic 2 O(n) -time and -space algorithms for solving exact SVP, and exact CVP when the target point is sufficiently close to the lattice, on n-dimensional lattices in any (semi-)norm given an M-ellipsoid of the unit ball. In many norms of interest, including all ℓ p norms, an M-ellipsoid is computable in deterministic poly(n) time, in which case these algorithms are fully deterministic. Here our approach may be seen as a derandomization of the "AKS sieve" for exact SVP and CVP (Ajtai, Kumar, and Siva Kumar, STOC2001 and CCC 2002). As a further application of our SVP algorithm, we derive an expected O(f*(n)) n -time algorithm for Integer Programming, where f*(n) denotes the optimal bound in the so-called "flatnesstheorem, " which satisfies f*(n) = O(n 4/3 polylog(n))and is conjectured to be f*(n) = O(n). Our runtime improves upon the previous best of O(n 2 ) n by Hildebrand and Koppe (2010).

Details

FOCS Conference 2010 Conference Paper

Learning Convex Concepts from Gaussian Distributions with PCA

  • Santosh S. Vempala

We present a new algorithm for learning a convex set in n-dimensional space given labeled examples drawn from any Gaussian distribution. The complexity of the algorithm is bounded by a fixed polynomial in n times a function of k and ϵ where k is the dimension of the normal subspace (the span of normal vectors to supporting hyperplanes of the convex set) and the output is a hypothesis that correctly classifies at least 1 - ϵ of the unknown Gaussian distribution. For the important case when the convex set is the intersection of k halfspaces, the complexity is poly(n, k, 1/ϵ) + n · min k(O(log k/ϵ 4 )), (k/ϵ) O(k), improving substantially on the state of the art [Vem04], [KOS08] for Gaussian distributions. The key step of the algorithm is a Singular Value Decomposition after applying a normalization. The proof is based on a monotonicity property of Gaussian space under convex restrictions.

Details

STOC Conference 2008 Conference Paper

A discriminative framework for clustering via similarity functions

  • Maria-Florina Balcan
  • Avrim Blum
  • Santosh S. Vempala

Problems of clustering data from pairwise similarity information are ubiquitous in Computer Science. Theoretical treatments typically view the similarity information as ground-truth and then design algorithms to (approximately) optimize various graph-based objective functions. However, in most applications, this similarity information is merely based on some heuristic; the ground truth is really the unknown correct clustering of the data points and the real goal is to achieve low error on the data. In this work, we develop a theoretical approach to clustering from this perspective. In particular, motivated by recent work in learning theory that asks "what natural properties of a similarity (or kernel) function are sufficient to be able to learn well?" we ask "what natural properties of a similarity function are sufficient to be able to cluster well?"

Details

FOCS Conference 2008 Conference Paper

Isotropic PCA and Affine-Invariant Clustering

  • S. Charles Brubaker
  • Santosh S. Vempala

We present an extension of Principal Component Analysis (PCA) and a new algorithm for clustering points in $\R^n$ based on it. The key property of the algorithm is that it is affine-invariant. When the input is a sample from a mixture of two arbitrary Gaussians, the algorithm correctly classifies the sample assuming only that the two components are separable by a hyperplane, i. e. , there exists a halfspace that contains most of one Gaussian and almost none of the other in probability mass. This is nearly the best possible, improving known results substantially. For k≫2 components, the algorithm requires only that there be some (k-1)-dimensional subspace in which the ``overlap'' in every direction is small. Our main tools are isotropic transformation, spectral projection and a simple reweighting technique. We call this combination isotropic PCA.

Details

STOC Conference 2008 Conference Paper

Logconcave random graphs

  • Alan M. Frieze
  • Santosh S. Vempala
  • Juan Vera 0001

We propose the following model of a random graph on n vertices. Let F be a distribution in R + n(n-1)/2 with a coordinate for every pair ij with 1 ≤ i,j ≤ n. Then G F,p is the distribution on graphs with n vertices obtained by picking a random point X from F and defining a graph on n vertices whose edges are pairs ij for which X ij ≤ p. The standard Erdos-Renyi model is the special case when F is uniform on the 0-1 unit cube. We determine basic properties such as the connectivity threshold for quite general distributions. We also consider cases where the X ij are the edge weights in some random instance of a combinatorial optimization problem. By choosing suitable distributions, we can capture random graphs with interesting properties such as triangle-free random graphs and weighted random graphs with bounded total weight.

Details

FOCS Conference 2007 Conference Paper

Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting

  • Daniel Stefankovic
  • Santosh S. Vempala
  • Eric Vigoda

We present a near-optimal reduction from approximately counting the cardinality of a discrete set to approximately sampling elements of the set. An important application of our work is to approximating the partition function Z of a discrete system, such as the Ising model, matchings or colorings of a graph. The standard approach to estimating the partition function Z(\beta *) at some desired inverse temperature \beta * is to define a sequence, which we call a cooling schedule, \beta 0 = 0 \le \beta 1 \le \cdots \le \beta \ell = \beta * where Z(0) is trivial to compute and the ratios Z(\beta i + 1)/Z(\beta i) are easy to estimate by sampling from the distribution corresponding to Z(\beta i). Previous approaches required a cooling schedule of length {\rm O}*(1nA) where A = Z(0), thereby ensuring that each ratio Z(\beta i + 1)/Z(\beta i) is bounded. We present a cooling schedule of length \ell = {\rm O}*\left( {\sqrt {1nA} } \right). For well-studied problems such as estimating the partition function of the Ising model, or approximating the number of colorings or matchings of a graph, our cooling schedule is of length {\rm O}*\left( {\sqrt n } \right) and the total number of samples required is {\rm O}*\left( n \right). This implies an overall savings of a factor of roughly n in the running time of the approximate counting algorithm compared to the previous best approach. A similar improvement in the length of the cooling schedule was recently obtained by Lovász and Vempala in the context of estimating the volume of convex bodies. While our reduction is inspired by theirs, the discrete analogue of their result turns out to be significantly more difficult. Whereas a fixed schedule suffices in their setting, we prove that in the discrete setting we need an adaptive schedule, i. e. , the schedule depends on Z. More precisely, we prove any non-adaptive cooling schedule has length at least {\rm O}*\left( {1nA} \right), and we present an algorithm to find an adaptive schedule of length {\rm O}*\left( {\sqrt {1nA} } \right) and a nearly matching lower bound.

Details

FOCS Conference 2006 Conference Paper

Dispersion of Mass and the Complexity of Randomized Geometric Algorithms

  • Luis Rademacher
  • Santosh S. Vempala

How much can randomness help computation? Motivated by this general question and by volume computation, one of the few instances where randomness provably helps, we analyze a notion of dispersion and connect it to asymptotic convex geometry. We obtain a nearly quadratic lower bound on the complexity of randomized volume algorithms for convex bodies in Ropf n (the current best algorithm has complexity roughly n 4, conjectured to be n 3 ). Our main tools, dispersion of random determinants and dispersion of the length of a random point from a convex body, are of independent interest and applicable more generally; in particular, the latter is closely related to the variance hypothesis from convex geometry. This geometric dispersion also leads to lower bounds for matrix problems and property testing

Details

FOCS Conference 2006 Conference Paper

Fast Algorithms for Logconcave Functions: Sampling, Rounding, Integration and Optimization

  • László Lovász 0001
  • Santosh S. Vempala

We prove that the hit-and-run random walk is rapidly mixing for an arbitrary logconcave distribution starting from any point in the support. This extends the work of Lovasz and Vempala (2004), where this was shown for an important special case, and settles the main conjecture formulated there. From this result, we derive asymptotically faster algorithms in the general oracle model for sampling, rounding, integration and maximization of logconcave functions, improving or generalizing the main results of Lovasz and Vempala (2003), Applegate and Kannan (1990) and Kalai and Vempala respectively. The algorithms for integration and optimization both use sampling and are surprisingly similar

Details

FOCS Conference 2005 Conference Paper

Nash Equilibria in Random Games

  • Imre Bárány
  • Santosh S. Vempala
  • Adrian Vetta

We consider Nash equilibria in 2-player random games and analyze a simple Las Vegas algorithm for finding an equilibrium. The algorithm is combinatorial and always finds a Nash equilibrium; on m /spl times/ n payoff matrices, it runs in time O(m/sup 2/n log log n + n/sup 2/m log log m) with high probability. Our main tool is a polytope formulation of equilibria.

Details

STOC Conference 2005 Conference Paper

Tensor decomposition and approximation schemes for constraint satisfaction problems

  • Wenceslas Fernandez de la Vega
  • Marek Karpinski
  • Ravindran Kannan
  • Santosh S. Vempala

The only general class of MAX-rCSP problems for which Polynomial Time Approximation Schemes (PTAS) are known are the dense problems. In this paper, we give PTAS's for a much larger class of weighted MAX-rCSP problems which includes as special cases the dense problems and, for r = 2, all metric instances (where the weights satisfy the triangle inequality) and quasimetric instances; for r > 2, our class includes a generalization of metrics. Our algorithms are based on low-rank approximations with two novel features: (1) a method of approximating a tensor by the sum of a small number of "rank-1" tensors, akin to the traditional Singular Value Decomposition (this might be of independent interest) and (2) a simple way of scaling the weights. Besides MAX-rCSP problems, we also give PTAS's for problems with a constant number of global constraints such as maximum weighted graph bisection and some generalizations.

Details

STOC Conference 2004 Conference Paper

A simple polynomial-time rescaling algorithm for solving linear programs

  • John Dunagan
  • Santosh S. Vempala

The perceptron algorithm, developed mainly in the machine learning literature, is a simple greedy method for finding a feasible solution to a linear program (alternatively, for learning a threshold function. ). In spite of its exponential worst-case complexity, it is often quite useful, in part due to its noise-tolerance and also its overall simplicity. In this paper, we show that a randomized version of the perceptron algorithm with periodic rescaling runs in polynomial-time. The resulting algorithm for linear programming has an elementary description and analysis.

Details

STOC Conference 2004 Conference Paper

Hit-and-run from a corner

  • László Lovász 0001
  • Santosh S. Vempala

We show that the hit-and-run random walk mixes rapidly starting from any interior point of a convex body. This is the first random walk known to have this property. In contrast, the ball walk can take exponentially many steps from some starting points.

Details

FOCS Conference 2003 Conference Paper

Logconcave Functions: Geometry and Efficient Sampling Algorithms

  • László Lovász 0001
  • Santosh S. Vempala

The class of logconcave functions in R/sup n/ is a common generalization of Gaussians and of indicator functions of convex sets. Motivated by the problem of sampling from a logconcave density function, we study their geometry and introduce an analysis technique for "smoothing" them out. This leads to efficient sampling algorithms with no assumptions on the local smoothness of the density function. After appropriate preprocessing, both the ball walk (with a Metropolis filter) and a generalization of hit-and-run produce a point from approximately the right distribution in time O*(n/sup 4/), and in amortized time O*(n/sup 3/) if many sample points are needed (where the asterisk indicates that dependence on the error parameter and factors of log n are not shown). The bounds are optimal in terms of a "roundness" parameter and match the best-known bounds for the special case of the uniform density over a convex set.

Details

FOCS Conference 2003 Conference Paper

Simulated Annealing in Convex Bodies and an 0*(n4) Volume Algorithm

  • László Lovász 0001
  • Santosh S. Vempala

We present a new algorithm for computing the volume of a convex body in R/sup n/. The main ingredient of the algorithm is a "morphing" technique that can be viewed as a variant of simulated annealing. Its complexity is O*(n/sup 4/), improving on the previous best algorithm by a factor of n.

Details

FOCS Conference 2002 Conference Paper

A Spectral Algorithm for Learning Mixtures of Distributions

  • Santosh S. Vempala
  • Grant Wang

We show that a simple spectral algorithm for learning a mixture of k spherical Gaussians in /spl Ropf//sup n/ works remarkably well - it succeeds in identifying the Gaussians assuming essentially the minimum possible separation between their centers that keeps them unique. The sample complexity and running time are polynomial in both n and k. The algorithm also works for the more general problem of learning a mixture of "weakly isotropic" distributions (e. g. a mixture of uniform distributions on cubes).

Details

STOC Conference 2002 Conference Paper

Approximation algorithms for minimum-cost k-vertex connected subgraphs

  • Joseph Cheriyan
  • Santosh S. Vempala
  • Adrian Vetta

(MATH) We present two new algorithms for the problem of finding a minimum-cost k -vertex connected spanning subgraph. The first algorithm works on undirected graphs with at least 6k 2 vertices and achieves an approximation factor of 6 times the k th harmonic number, which is $O(\log k)$. The second algorithm works on directed and undirected graphs. It gives an $O(\sqrt{ n /\keps})$-approximation algorithm for any $\keps > 0$ and $k \le (1-\keps)n$. The latter algorithm also extends to other problems in network design with vertex connectivity requirements. Our main tools are setpair relaxations, a theorem of Mader's (in the undirected case) and iterative rounding (general case).

Details

STOC Conference 2002 Conference Paper

Solving convex programs by random walks

  • Dimitris Bertsimas
  • Santosh S. Vempala

In breakthrough developments about two decades ago, L. G. Khachiyan [14] showed that the Ellipsoid method solves linear programs in polynomial time, while M. Grötschel, L. Lovász and A. Schrijver [4, 5] extended this to the problem of minimizing a convex function over any convex set specified by a separation oracle. In 1996, P. M. Vaidya [21] improved the running time via a more sophisticated algorithm. We present a simple new algorithm for convex optimization based on sampling by a random walk; it also solves for a natural generalization of the problem.

Details

STOC Conference 2001 Conference Paper

Optimal outlier removal in high-dimensional

  • John Dunagan
  • Santosh S. Vempala

We study the problem of finding an outlier-free subset of a set of points (or a probability distribution) in n -dimensional Euclidean space. A point x is defined to be a β-outlier if there exists some direction w in which its squared distance from the mean along w is greater than β times the average squared distance from the mean along w [1]. Our main theorem is that for any ε>0, there exists a (1-ε) fraction of the original distribution that has no O (\frac{ n }{ε}( b +log \frac{ n }{ε))-outliers, improving on the previous bound of O(n ^7 b /ε). This bound is shown to be nearly the best possible. The theorem is constructive, and results in a \frac{1}{1-ε} approximation to the following optimization problem: given a distribution μ (i.e. the ability to sample from it), and a parameter ε>0, find the minimum β for which there exists a subset of probability at least (1-ε) with no β-outliers.

Details

FOCS Conference 2000 Conference Paper

Efficient Algorithms for Universal Portfolios

  • Adam Tauman Kalai
  • Santosh S. Vempala

A constant rebalanced portfolio is an investment strategy which keeps the same distribution of wealth among a set of stocks from day to day. There has been much work on Cover's Universal algorithm, which is competitive with the best constant rebalanced portfolio determined in hindsight (D. Helmbold et al. , 1995; A. Blum and A. Kalai, 1999; T. M. Cover and E. Ordentlich, 1996). While this algorithm has good performance guarantees, all known implementations are exponential in the number of stocks, restricting the number of stocks used in experiments. We present an efficient implementation of the Universal algorithm that is based on non-uniform random walks that are rapidly mixing (D. Applegate and R. Kannanm, 1991). This same implementation also works for non-financial applications of the Universal algorithm, such as data compression (T. M. Cover, 1886) and language modeling (A. Kalai et al. , 1999).

Details

FOCS Conference 2000 Conference Paper

On Clusterings - Good, Bad and Spectral

  • Ravindran Kannan
  • Santosh S. Vempala
  • Adrian Vetta

We propose a new measure for assessing the quality of a clustering. A simple heuristic is shown to give worst-case guarantees under the new measure. Then we present two results regarding the quality of the clustering found by a popular spectral algorithm. One proffers worst case guarantees whilst the other shows that if there exists a "good" clustering then the spectral algorithm will find one close to it.

Details

FOCS Conference 1999 Conference Paper

An Algorithmic Theory of Learning: Robust Concepts and Random Projection

  • Rosa I. Arriaga
  • Santosh S. Vempala

We study the phenomenon of cognitive learning from an algorithmic standpoint. How does the brain effectively learn concepts from a small number of examples despite the fact that each example contains a huge amount of information? We provide a novel analysis for a model of robust concept learning (closely related to "margin classifiers"), and show that a relatively small number of examples are sufficient to learn rich concept classes (including threshold functions, Boolean formulae and polynomial surfaces). As a result, we obtain simple intuitive proofs for the generalization bounds of Support Vector Machines. In addition, the new algorithm has several advantages-they are faster conceptually simpler and highly resistant to noise. For example, a robust half-space can be PAC-learned in linear time using only a constant number of training examples, regardless of the number of attributes. A general (algorithmic) consequence of the model, that "more robust concepts are easier to learn", is supported by a multitude of psychological studies.

Details

FOCS Conference 1998 Conference Paper

Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations

  • Alan M. Frieze
  • Ravindran Kannan
  • Santosh S. Vempala

In several applications, the data consists of an m/spl times/n matrix A and it is of interest to find an approximation D of a specified rank k to A where, k is much smaller than m and n. Traditional methods like the Singular Value Decomposition (SVD) help us find the "best" such approximation. However, these methods take time polynomial in m, n which is often too prohibitive. In this paper, we develop an algorithm which is qualitatively faster provided we may sample the entries of the matrix according to a natural probability distribution. Indeed, in the applications such sampling is possible. Our main result is that we can find the description of a matrix D* of rank at most k so that /spl par/A-D*/spl par//sub F//spl les/min/D, rank(D)/spl les/k/spl par/A-D/spl par//sub F/+/spl epsiv//spl par/A/spl par//sub F/ holds with probability at least 1-/spl delta/. (For any matrix M, /spl par/M/spl par//sub F//sup 2/ denotes the sum of the squares of all the entries of M.) The algorithm takes time polynomial in k, 1//spl epsiv/, log(1//spl delta/) only, independent of m, n.

Details

FOCS Conference 1998 Conference Paper

Random Projection: A New Approach to VLSI Layout

  • Santosh S. Vempala

We show that random projection, the technique of projecting a set of points to a randomly chosen low-dimensional subspace, can be used to solve problems in VLSI layout. Specifically, for the problem of laying out a graph on a 2-dimensional grid so as to minimize the maximum edge length, we obtain an O(log/sup 3. 5/ n) approximation algorithm (this is the first o(n) approximation), and for the bicriteria problem of minimizing the total edge length while keeping the maximum length bounded, we obtain an O(log/sup 3/ n, log/sup 3. 5/ n) approximation. Our algorithms also work for d-dimensional versions of these problems (for any fixed d) with polylog approximation guarantees. Besides random projection, the main components of the algorithms are a linear programming relaxation, and volume-respecting Euclidean embeddings.

Details

FOCS Conference 1997 Conference Paper

A Random Sampling Based Algorithm for Learning the Intersection of Half-spaces

  • Santosh S. Vempala

We present an algorithm for learning the intersection of half spaces in n dimensions. Over nearly uniform distributions, it runs in polynomial time for up to O(logn/loglogn) half spaces or, more generally for any number of half spaces whose normal vectors lie in an O(log n/log log n) dimensional subspace. Over less restricted "non-concentrated" distributions it runs in polynomial time for a constant number of half spaces. This generalizes an earlier result of A. Blum and R. Kannan (1993). The algorithm is simple and is based on random sampling.

Details

FOCS Conference 1996 Conference Paper

A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions

  • Avrim Blum
  • Alan M. Frieze
  • Ravindran Kannan
  • Santosh S. Vempala

The authors consider the problem of learning a linear threshold function (a halfspace in n dimensions, also called a "perceptron"). Methods for solving this problem generally fall into two categories. In the absence of noise, this problem can be formulated as a linear program and solved in polynomial time with the ellipsoid algorithm (or interior point methods). On the other hand, simple greedy algorithms such as the perceptron algorithm seem to work well in practice and can be made noise tolerant; but, their running time depends on a separation parameter (which quantifies the amount of "wiggle room" available) and can be exponential in the description length of the input. They show how simple greedy methods can be used to find weak hypotheses (hypotheses that classify noticeably more than half of the examples) in polynomial time, without dependence on any separation parameter. This results in a polynomial-time algorithm for learning linear threshold functions in the PAC model in the presence of random classification noise. The algorithm is based on a new method for removing outliers in data. Specifically, for any set S of points in R/sup n/, each given to b bits of precision, they show that one can remove only a small fraction of S so that in the remaining set T, for every vector v, max/sub x/spl epsiv/T/(v/spl middot/x)/sup 2//spl les/poly(n, b)|T|/sup -1//spl Sigma//sub x/spl epsiv/T/(v/spl middot/x)/sup 2/. After removing these outliers, they are able to show that a modified version of the perceptron learning algorithm works in polynomial time, even in the presence of random classification noise.

Details
v2026.09.13