<?xml version="1.0" encoding="UTF-8"?>
 <rdf:RDF xmlns="http://purl.org/rss/1.0/" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:taxo="http://purl.org/rss/1.0/modules/taxonomy/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:cc="http://web.resource.org/cc/" xmlns:syn="http://purl.org/rss/1.0/modules/syndication/" xmlns:admin="http://webns.net/mvcb/">
  <channel rdf:about="http://pinboard.in">
    <title>Pinboard (arsyed)</title>
    <link>https://pinboard.in/u:arsyed/public/</link>
    <description>recent bookmarks from arsyed</description>
    <items>
      <rdf:Seq>	<rdf:li rdf:resource="https://arxiv.org/abs/1905.12558"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1907.01507"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1906.08158"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1902.04023"/>
	<rdf:li rdf:resource="http://book.bionumbers.org/"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1806.06323"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1704.01652"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1610.09726"/>
	<rdf:li rdf:resource="http://www.sciencedirect.com/science/article/pii/S0167637703000622"/>
	<rdf:li rdf:resource="http://www.decisionsciencenews.com/2016/06/17/cant-compute-standard-deviation-head-divide-range-four/"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1601.00013#"/>
	<rdf:li rdf:resource="https://www.edx.org/course/street-fighting-math-mitx-6-sfmx"/>
	<rdf:li rdf:resource="http://web.mit.edu/sanjoy/www/"/>
	<rdf:li rdf:resource="https://github.com/facebookresearch/pysparnn"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1602.07860"/>
	<rdf:li rdf:resource="https://groups.csail.mit.edu/sls/publications/2015/LeoLiu_MEng-Thesis.pdf"/>
	<rdf:li rdf:resource="http://www.cs.cmu.edu/~avrim/Approx00/lectures/lect0216"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1510.00215"/>
	<rdf:li rdf:resource="http://dl.acm.org/citation.cfm?id=1496829"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1010.1945"/>
	<rdf:li rdf:resource="http://timvieira.github.io/blog/post/2014/08/07/complex-step-derivative/"/>
	<rdf:li rdf:resource="https://www.ideals.illinois.edu/bitstream/handle/2142/46738/Alina_Ene.pdf?sequence=1"/>
	<rdf:li rdf:resource="http://www.cs.ubc.ca/~nickhar/W13/"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1304.4948"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1408.2051"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1205.1477"/>
	<rdf:li rdf:resource="http://link.springer.com/chapter/10.1007%2FBFb0121195"/>
	<rdf:li rdf:resource="http://link.springer.com/article/10.1007/BF01588971"/>
	<rdf:li rdf:resource="http://jmlr.org/proceedings/papers/v37/leng15.html"/>
	<rdf:li rdf:resource="http://www.dbs.ifi.lmu.de/~renz/technicalReports/uncertainTimeSeries.pdf"/>
	<rdf:li rdf:resource="http://www.mit.edu/~mahabadi/sm-thesis.pdf"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1404.1578"/>
	<rdf:li rdf:resource="http://www.cs.yale.edu/homes/el327/datamining2013a.html"/>
	<rdf:li rdf:resource="http://www.nada.kth.se/~viggo/problemlist/compendium.html"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1110.3767"/>
	<rdf:li rdf:resource="http://mittheory.wordpress.com/2013/11/22/beyond-lsh/"/>
	<rdf:li rdf:resource="http://theoryofcomputing.org/articles/v008a014/"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1408.3060"/>
	<rdf:li rdf:resource="http://math.stackexchange.com/questions/38480/how-much-does-symbolic-integration-mean-to-mathematics/"/>
	<rdf:li rdf:resource="http://www.cs.ucr.edu/~neal/"/>
	<rdf:li rdf:resource="http://greedyalgs.info/blog/"/>
	<rdf:li rdf:resource="http://matthias.vallentin.net/blog/2011/06/a-garden-variety-of-bloom-filters/"/>
	<rdf:li rdf:resource="http://www.johndcook.com/blog/2011/06/10/stirling-approximation/?"/>
	<rdf:li rdf:resource="http://www.designofapproxalgs.com/"/>
	<rdf:li rdf:resource="http://dialinf.wordpress.com/2007/12/17/commented-out/"/>
	<rdf:li rdf:resource="http://www.johndcook.com/blog/2010/08/16/how-to-compute-log-factorial/"/>
	<rdf:li rdf:resource="http://www.johndcook.com/blog/2010/07/27/sine-approximation-for-small-x/"/>
	<rdf:li rdf:resource="http://pages.cs.wisc.edu/~shuchi/courses/880-S07/"/>
	<rdf:li rdf:resource="http://www.johndcook.com/blog/2010/04/29/simple-approximation-to-normal-distribution/?utm_source=feedburner&amp;utm_medium=feed&amp;utm_campaign=Feed%3A+TheEndeavour+(The+Endeavour)"/>
	<rdf:li rdf:resource="http://www.johndcook.com/blog/2009/06/29/bancrofts-rule/"/>
	<rdf:li rdf:resource="http://www.johndcook.com/blog/2009/06/25/probability-approximation/"/>
	<rdf:li rdf:resource="http://www.johndcook.com/blog/2009/02/12/sums-of-uniform-random-values/"/>
	<rdf:li rdf:resource="http://www.johndcook.com/blog/2009/02/10/rolling-dice-for-normal-samples/"/>
	<rdf:li rdf:resource="http://scienceblogs.com/builtonfacts/2009/02/sunday_function_21.php"/>
	<rdf:li rdf:resource="http://www.johndcook.com/relative_error_normal_approx.html"/>
	<rdf:li rdf:resource="http://geomblog.blogspot.com/2008/07/concept-of-approximation.html"/>
	<rdf:li rdf:resource="http://mit.edu/18.098/"/>
	<rdf:li rdf:resource="http://www.vendian.org/envelope/dir2/day_of_dots_clock/?do=20:01:39"/>
      </rdf:Seq>
    </items>
  </channel><item rdf:about="https://arxiv.org/abs/1905.12558">
    <title>[1905.12558] Limitations of the Empirical Fisher Approximation</title>
    <dc:date>2019-08-06T16:56:23+00:00</dc:date>
    <link>https://arxiv.org/abs/1905.12558</link>
    <dc:creator>arsyed</dc:creator><description><![CDATA["     Natural gradient descent, which preconditions a gradient descent update with the Fisher information matrix of the underlying statistical model, is a way to capture partial second-order information. Several highly visible works have advocated an approximation known as the empirical Fisher, drawing connections between approximate second-order methods and heuristics like Adam. We dispute this argument by showing that the empirical Fisher---unlike the Fisher---does not generally capture second-order information. We further argue that the conditions under which the empirical Fisher approaches the Fisher (and the Hessian) are unlikely to be met in practice, and that, even on simple optimization problems, the pathologies of the empirical Fisher can have undesirable effects. "]]></description>
<dc:subject>fisher-information approximation natural-gradient</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:96ee91794ee5/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:fisher-information"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:natural-gradient"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1907.01507">
    <title>[1907.01507] Best k-layer neural network approximations</title>
    <dc:date>2019-07-07T14:49:46+00:00</dc:date>
    <link>https://arxiv.org/abs/1907.01507</link>
    <dc:creator>arsyed</dc:creator><description><![CDATA[We investigate the geometry of the empirical risk minimization problem for k-layer neural networks. We will provide examples showing that for the classical activation functions σ(x)=1/(1+exp(−x)) and σ(x)=tanh(x), there exists a positive-measured subset of target functions that do not have best approximations by a fixed number of layers of neural networks. In addition, we study in detail the properties of shallow networks, classifying cases when a best k-layer neural network approximation always exists or does not exist for the ReLU activation σ=max(0,x). We also determine the dimensions of shallow ReLU-activated networks. ]]></description>
<dc:subject>neural-net approximation</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:cace357cc1cf/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:neural-net"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1906.08158">
    <title>[1906.08158] BatchBALD: Efficient and Diverse Batch Acquisition for Deep Bayesian Active Learning</title>
    <dc:date>2019-06-26T16:05:39+00:00</dc:date>
    <link>https://arxiv.org/abs/1906.08158</link>
    <dc:creator>arsyed</dc:creator><description><![CDATA[We develop BatchBALD, a tractable approximation to the mutual information between a batch of points and model parameters, which we use as an acquisition function to select multiple informative points jointly for the task of deep Bayesian active learning. BatchBALD is a greedy linear-time 1−1e-approximate algorithm amenable to dynamic programming and efficient caching. We compare BatchBALD to the commonly used approach for batch data acquisition and find that the current approach acquires similar and redundant points, sometimes performing worse than randomly acquiring data. We finish by showing that, using BatchBALD to consider dependencies within an acquisition batch, we achieve new state of the art performance on standard benchmarks, providing substantial data efficiency improvements in batch acquisition. ]]></description>
<dc:subject>active-learning bayesian deep-learning approximation</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:5b6391b842da/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:active-learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:bayesian"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:deep-learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1902.04023">
    <title>[1902.04023] Computing Extremely Accurate Quantiles Using t-Digests</title>
    <dc:date>2019-02-18T16:12:31+00:00</dc:date>
    <link>https://arxiv.org/abs/1902.04023</link>
    <dc:creator>arsyed</dc:creator><description><![CDATA[}We present on-line algorithms for computing approximations of rank-based statistics that give high accuracy, particularly near the tails of a distribution, with very small sketches. Notably, the method allows a quantile q to be computed with an accuracy relative to max(q,1−q) rather than absolute accuracy as with most other methods. This new algorithm is robust with respect to skewed distributions or ordered datasets and allows separately computed summaries to be combined with no loss in accuracy.
An open-source Java implementation of this algorithm is available from the author. Independent implementations in Go and Python are also available."]]></description>
<dc:subject>algorithms online approximation quantile via:jm data-structures t-digest sketching</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:995c5c243542/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:online"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:quantile"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:via:jm"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:data-structures"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:t-digest"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:sketching"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://book.bionumbers.org/">
    <title>Cell Biology by the Numbers</title>
    <dc:date>2018-10-23T15:21:00+00:00</dc:date>
    <link>http://book.bionumbers.org/</link>
    <dc:creator>arsyed</dc:creator><description><![CDATA["Vignettes that reveal how numbers serve as a sixth sense to understanding our cells"]]></description>
<dc:subject>biology numbers scale approximation books numeracy .* rec</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:d299c0835ebe/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:biology"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:numbers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:scale"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:books"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:numeracy"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:.*"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:rec"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1806.06323">
    <title>[1806.06323] Approximate Submodular Functions and Performance Guarantees</title>
    <dc:date>2018-06-28T08:41:51+00:00</dc:date>
    <link>https://arxiv.org/abs/1806.06323</link>
    <dc:creator>arsyed</dc:creator><description><![CDATA[We consider the problem of maximizing non-negative non-decreasing set functions. Although most of the recent work focus on exploiting submodularity, it turns out that several objectives we encounter in practice are not submodular. Nonetheless, often we leverage the greedy algorithms used in submodular functions to determine a solution to the non-submodular functions. Hereafter, we propose to address the original problem by \emph{approximating} the non-submodular function and analyze the incurred error, as well as the performance trade-offs. To quantify the approximation error, we introduce a novel concept of δ-approximation of a function, which we used to define the space of submodular functions that lie within an approximation error. We provide necessary conditions on the existence of such δ-approximation functions, which might not be unique. Consequently, we characterize this subspace which we refer to as \emph{region of submodularity}. Furthermore, submodular functions are known to lead to different sub-optimality guarantees, so we generalize those dependencies upon a δ-approximation into the notion of \emph{greedy curvature}. Finally, we used this latter notion to simplify some of the existing results and efficiently (i.e., linear complexity) determine tightened bounds on the sub-optimality guarantees using objective functions commonly used in practical setups and validate them using real data.]]></description>
<dc:subject>submodularity approximation</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:be16df87d423/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:submodularity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1704.01652">
    <title>[1704.01652] Greed is Good: Near-Optimal Submodular Maximization via Greedy Optimization</title>
    <dc:date>2017-04-11T14:51:29+00:00</dc:date>
    <link>https://arxiv.org/abs/1704.01652</link>
    <dc:creator>arsyed</dc:creator><description><![CDATA["It is known that greedy methods perform well for maximizing monotone submodular functions. At the same time, such methods perform poorly in the face of non-monotonicity. In this paper, we show - arguably, surprisingly - that invoking the classical greedy algorithm O(k√)-times leads to the (currently) fastest deterministic algorithm, called Repeated Greedy, for maximizing a general submodular function subject to k-independent system constraints. Repeated Greedy achieves (1+O(1/k√))k approximation using O(nrk√) function evaluations (here, n and r denote the size of the ground set and the maximum size of a feasible solution, respectively). We then show that by a careful sampling procedure, we can run the greedy algorithm only once and obtain the (currently) fastest randomized algorithm, called Sample Greedy, for maximizing a submodular function subject to k-extendible system constraints (a subclass of k-independent system constrains). Sample Greedy achieves (k+3)-approximation with only O(nr/k) function evaluations. Finally, we derive an almost matching lower bound, and show that no polynomial time algorithm can have an approximation ratio smaller than k+1/2−ε. To further support our theoretical results, we compare the performance of Repeated Greedy and Sample Greedy with prior art in a concrete application (movie recommendation). We consistently observe that while Sample Greedy achieves practically the same utility as the best baseline, it performs at least two orders of magnitude faster."]]></description>
<dc:subject>papers submodularity optimization algorithms greedy approximation</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:ceb753b49998/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:submodularity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:greedy"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1610.09726">
    <title>[1610.09726] The Multi-fidelity Multi-armed Bandit</title>
    <dc:date>2016-11-05T23:44:48+00:00</dc:date>
    <link>https://arxiv.org/abs/1610.09726</link>
    <dc:creator>arsyed</dc:creator><description><![CDATA["We study a variant of the classical stochastic K-armed bandit where observing the outcome of each arm is expensive, but cheap approximations to this outcome are available. For example, in online advertising the performance of an ad can be approximated by displaying it for shorter time periods or to narrower audiences. We formalise this task as a multi-fidelity bandit, where, at each time step, the forecaster may choose to play an arm at any one of M fidelities. The highest fidelity (desired outcome) expends cost λ(m). The mth fidelity (an approximation) expends λ(m)<λ(M) and returns a biased estimate of the highest fidelity. We develop MF-UCB, a novel upper confidence bound procedure for this setting and prove that it naturally adapts to the sequence of available approximations and costs thus attaining better regret than naive strategies which ignore the approximations. For instance, in the above online advertising example, MF-UCB would use the lower fidelities to quickly eliminate suboptimal ads and reserve the larger expensive experiments on a small set of promising candidates. We complement this result with a lower bound and show that MF-UCB is nearly optimal under certain conditions."]]></description>
<dc:subject>papers bandits cost resource fidelity algorithms approximation</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:846e2f9cf991/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:bandits"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:cost"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:resource"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:fidelity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.sciencedirect.com/science/article/pii/S0167637703000622">
    <title>A note on maximizing a submodular set function subject to a knapsack constraint</title>
    <dc:date>2016-08-14T18:57:18+00:00</dc:date>
    <link>http://www.sciencedirect.com/science/article/pii/S0167637703000622</link>
    <dc:creator>arsyed</dc:creator><description><![CDATA[In this paper, we obtain an (1−e−1)-approximation algorithm for maximizing a nondecreasing submodular set function subject to a knapsack constraint. This algorithm requires O(n5) function value computations.

]]></description>
<dc:subject>papers submodularity optimization knapsack algorithms approximation</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:b4cacb6edae8/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:submodularity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:knapsack"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.decisionsciencenews.com/2016/06/17/cant-compute-standard-deviation-head-divide-range-four/">
    <title>Can’t compute the standard deviation in your head? Divide the range by four.</title>
    <dc:date>2016-07-16T15:49:45+00:00</dc:date>
    <link>http://www.decisionsciencenews.com/2016/06/17/cant-compute-standard-deviation-head-divide-range-four/</link>
    <dc:creator>arsyed</dc:creator><dc:subject>statistics variance approximation heuristic calculation tricks</dc:subject>
<dc:identifier>https://pinboard.in/u:arsyed/b:f7ceb158e26b/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:variance"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:heuristic"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:calculation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:tricks"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1601.00013#">
    <title>[1601.00013] A single hidden layer feedforward network with only one neuron in the hidden layer can approximate any univariate function</title>
    <dc:date>2016-07-04T15:04:07+00:00</dc:date>
    <link>http://arxiv.org/abs/1601.00013#</link>
    <dc:creator>arsyed</dc:creator><description><![CDATA["The possibility of approximating a continuous function on a compact subset of the real line by a feedforward single hidden layer neural network with a sigmoidal activation function has been studied in many papers. Such networks can approximate an arbitrary continuous function provided that an unlimited number of neurons in a hidden layer is permitted. In this paper, we consider constructive approximation on any finite interval of ℝ by neural networks with only one neuron in the hidden layer. We construct algorithmically a smooth, sigmoidal, almost monotone activation function σ providing approximation to an arbitrary continuous function within any degree of accuracy. This algorithm is implemented in a computer program, which computes the value of σ at any reasonable point of the real axis."]]></description>
<dc:subject>papers neural-net approximation via:cshalizi</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:a7759cb4fc29/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:neural-net"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:via:cshalizi"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://www.edx.org/course/street-fighting-math-mitx-6-sfmx">
    <title>Street-Fighting Math | edX</title>
    <dc:date>2016-05-23T03:29:59+00:00</dc:date>
    <link>https://www.edx.org/course/street-fighting-math-mitx-6-sfmx</link>
    <dc:creator>arsyed</dc:creator><dc:subject>courses moocs math approximation .learn</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:4c7225186848/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:courses"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:moocs"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:math"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:.learn"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://web.mit.edu/sanjoy/www/">
    <title>Sanjoy Mahajan</title>
    <dc:date>2016-05-23T03:18:55+00:00</dc:date>
    <link>http://web.mit.edu/sanjoy/www/</link>
    <dc:creator>arsyed</dc:creator><dc:subject>people teaching learning math approximation heuristics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:1113a1f65499/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:people"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:teaching"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:math"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:heuristics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://github.com/facebookresearch/pysparnn">
    <title>facebookresearch/pysparnn: Approximate Nearest Neighbor Search for Sparse Data in Python!</title>
    <dc:date>2016-04-25T08:18:48+00:00</dc:date>
    <link>https://github.com/facebookresearch/pysparnn</link>
    <dc:creator>arsyed</dc:creator><dc:subject>python libs knn sparse search algorithms similarity facebook approximation</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:0524c975e89b/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:python"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:libs"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:knn"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:sparse"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:search"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:similarity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:facebook"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1602.07860">
    <title>[1602.07860] Probably Approximately Correct Greedy Maximization</title>
    <dc:date>2016-03-02T00:14:55+00:00</dc:date>
    <link>http://arxiv.org/abs/1602.07860</link>
    <dc:creator>arsyed</dc:creator><description><![CDATA["Submodular function maximization finds application in a variety of real-world decision-making problems. However, most existing methods, based on greedy maximization, assume it is computationally feasible to evaluate F, the function being maximized. Unfortunately, in many realistic settings F is too expensive to evaluate exactly even once. We present probably approximately correct greedy maximization, which requires access only to cheap anytime confidence bounds on F and uses them to prune elements. We show that, with high probability, our method returns an approximately optimal set. We propose novel, cheap confidence bounds for conditional entropy, which appears in many common choices of F and for which it is difficult to find unbiased or bounded estimates. Finally, results on a real-world dataset from a multi-camera tracking system in a shopping mall demonstrate that our approach performs comparably to existing methods, but at a fraction of the computational cost."]]></description>
<dc:subject>papers submodularity optimization approximation entropy conditional-entropy</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:3bfc0e840fa2/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:submodularity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:entropy"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:conditional-entropy"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://groups.csail.mit.edu/sls/publications/2015/LeoLiu_MEng-Thesis.pdf">
    <title>Acoustic Models for Speech Recognition Using Deep Neural Networks Based on Approximate Math</title>
    <dc:date>2016-02-28T21:50:40+00:00</dc:date>
    <link>https://groups.csail.mit.edu/sls/publications/2015/LeoLiu_MEng-Thesis.pdf</link>
    <dc:creator>arsyed</dc:creator><dc:subject>papers thesis speech dnn asr acoustic-model approximation</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:9a09fe044355/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:thesis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:speech"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:dnn"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:asr"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:acoustic-model"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.cs.cmu.edu/~avrim/Approx00/lectures/lect0216">
    <title>* Approximations using random projection -- approximate nearest neighbor.</title>
    <dc:date>2015-12-09T17:10:55+00:00</dc:date>
    <link>http://www.cs.cmu.edu/~avrim/Approx00/lectures/lect0216</link>
    <dc:creator>arsyed</dc:creator><dc:subject>notes algorithms approximation online random-projections ann knn</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:2afae18b9c3b/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:notes"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:online"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:random-projections"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:ann"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:knn"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1510.00215">
    <title>[1510.00215] FPT Approximation Schemes for Maximizing Submodular Functions</title>
    <dc:date>2015-10-06T03:29:18+00:00</dc:date>
    <link>http://arxiv.org/abs/1510.00215</link>
    <dc:creator>arsyed</dc:creator><description><![CDATA["We investigate the existence of approximation algorithms for maximization of submodular functions, that run in fixed parameter tractable (FPT) time. Given a non-decreasing submodular set function v:2X→ℝ the goal is to select a subset S of K elements from X such that v(S) is maximized. We identify three properties of set functions, referred to as p-separability properties, and we argue that many real-life problems can be expressed as maximization of submodular, p-separable functions, with low values of the parameter p. We present FPT approximation schemes for the minimization and maximization variants of the problem, for several parameters that depend on characteristics of the optimized set function, such as p and K. We confirm that our algorithms are applicable to a broad class of problems, in particular to problems from computational social choice, such as item selection or winner determination under several multiwinner election systems."]]></description>
<dc:subject>papers optimization approximation algorithms submodularity</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:d581d0c04841/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:submodularity"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://dl.acm.org/citation.cfm?id=1496829">
    <title>Approximating submodular functions everywhere</title>
    <dc:date>2015-08-02T05:42:25+00:00</dc:date>
    <link>http://dl.acm.org/citation.cfm?id=1496829</link>
    <dc:creator>arsyed</dc:creator><description><![CDATA["Submodular functions are a key concept in combinatorial optimization. Algorithms that involve submodular functions usually assume that they are given by a (value) oracle. Many interesting problems involving submodular functions can be solved using only polynomially many queries to the oracle, e.g., exact minimization or approximate maximization.

In this paper, we consider the problem of approximating a non-negative, monotone, submodular function f on a ground set of size n everywhere, after only poly(n) oracle queries. Our main result is a deterministic algorithm that makes poly(n) oracle queries and derives a function f such that, for every set S, f(S) approximates f(S) within a factor α(n), where α(n) = √n+1 for rank functions of matroids and α(n), = O(√n log n) for general monotone submodular functions. Our result is based on approximately finding a maximum volume inscribed ellipsoid in a symmetrized polymatroid, and the analysis involves various properties of submodular functions and polymatroids.

Our algorithm is tight up to logarithmic factors. Indeed, we show that no algorithm can achieve a factor better than Ω(√n/log n), even for rank functions of a matroid."]]></description>
<dc:subject>papers approximation submodularity</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:b5466e0f5db9/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:submodularity"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1010.1945">
    <title>[1010.1945] Submodular problems - approximations and algorithms</title>
    <dc:date>2015-07-22T04:41:38+00:00</dc:date>
    <link>http://arxiv.org/abs/1010.1945</link>
    <dc:creator>arsyed</dc:creator><description><![CDATA["We show that any submodular minimization (SM) problem defined on a linear constraint set with constraints having up to two variables per inequality, are 2-approximable in polynomial time. If the constraints are monotone (the two variables appear with opposite sign coefficients) then the problems of submodular minimization or supermodular maximization are polynomial time solvable. The key idea is to link these problems to a submodular s,t-cut problem defined here. This framework includes the problems: SM-vertex cover; SM-2SAT; SM-min satisfiability; SM-edge deletion for clique, SM-node deletion for biclique and others. We also introduce here the submodular closure problem and and show that it is solvable in polynomial time and equivalent to the submodular cut problem. All the results are extendible to multi-sets where each element of a set may appear with a multiplicity greater than 1. For all these NP-hard problems 2-approximations are the best possible in the sense that a better approximation factor cannot be achieved in polynomial time unless NP=P. The mechanism creates a relaxed "monotone" problem, solved as a submodular closure problem, the solution to which is mapped to a half integral super-optimal solution to the original problem. That half-integral solution has the persistency property meaning that integer valued variables retain their value in an optimal solution. This permits to delete the integer valued variables, and restrict the search of an optimal solution to the smaller set of remaining variables."]]></description>
<dc:subject>papers surveys algorithms approximation submodularity</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:33d38b4e767c/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:surveys"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:submodularity"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://timvieira.github.io/blog/post/2014/08/07/complex-step-derivative/">
    <title>Complex-step derivative</title>
    <dc:date>2015-07-12T21:21:33+00:00</dc:date>
    <link>http://timvieira.github.io/blog/post/2014/08/07/complex-step-derivative/</link>
    <dc:creator>arsyed</dc:creator><dc:subject>math complex gradient approximation tricks</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:7bb8bccf0f65/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:math"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:complex"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:gradient"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:tricks"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://www.ideals.illinois.edu/bitstream/handle/2142/46738/Alina_Ene.pdf?sequence=1">
    <title>APPROXIMATION ALGORITHMS FOR SUBMODULAR OPTIMIZATION AND GRAPH PROBLEMS</title>
    <dc:date>2015-07-03T07:54:39+00:00</dc:date>
    <link>https://www.ideals.illinois.edu/bitstream/handle/2142/46738/Alina_Ene.pdf?sequence=1</link>
    <dc:creator>arsyed</dc:creator><dc:subject>papers thesis algorithms approximation submodularity</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:ad0642a5302f/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:thesis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:submodularity"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.cs.ubc.ca/~nickhar/W13/">
    <title>CPSC 536N: Sparse Approximations</title>
    <dc:date>2015-07-01T22:21:07+00:00</dc:date>
    <link>http://www.cs.ubc.ca/~nickhar/W13/</link>
    <dc:creator>arsyed</dc:creator><description><![CDATA["This is a graduate course on algorithm design. We will explore two branches of this field: combinatorial optimization algorithms and spectral algorithms. The ultimate goal of the course is to explore the theme of “sparse approximations” in graph theory. We will discuss thin trees, thin forests, expanders and graph sparsifiers."]]></description>
<dc:subject>courses notes sparsity algorithms spectral-methods approximation graph discrete-optimization</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:9c80273b5710/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:courses"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:notes"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:sparsity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:spectral-methods"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:graph"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:discrete-optimization"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1304.4948">
    <title>[1304.4948] On the Approximation of Submodular Functions</title>
    <dc:date>2015-07-01T22:14:42+00:00</dc:date>
    <link>http://arxiv.org/abs/1304.4948</link>
    <dc:creator>arsyed</dc:creator><description><![CDATA["Submodular functions are a fundamental object of study in combinatorial optimization, economics, machine learning, etc. and exhibit a rich combinatorial structure. Many subclasses of submodular functions have also been well studied and these subclasses widely vary in their complexity. Our motivation is to understand the relative complexity of these classes of functions. Towards this, we consider the question of how well can one class of submodular functions be approximated by another (simpler) class of submodular functions. Such approximations naturally allow algorithms designed for the simpler class to be applied to the bigger class of functions. We prove both upper and lower bounds on such approximations. 
Our main results are: 
1. General submodular functions can be approximated by cut functions of directed graphs to a factor of n2/4, which is tight. 
2. General symmetric submodular functions1 can be approximated by cut functions of undirected graphs to a factor of n−1, which is tight up to a constant. 
3. Budgeted additive functions can be approximated by coverage functions to a factor of e/(e−1), which is tight. 
Here n is the size of the ground set on which the submodular function is defined. 
We also observe that prior works imply that monotone submodular functions can be approximated by coverage functions with a factor between O(n‾√logn) and Ω(n1/3/log2n)."]]></description>
<dc:subject>papers algorithms approximation complexity submodularity</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:e9c9072ac807/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:complexity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:submodularity"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1408.2051">
    <title>[1408.2051] Algorithms for Approximate Minimization of the Difference Between Submodular Functions, with Applications</title>
    <dc:date>2015-07-01T22:07:44+00:00</dc:date>
    <link>http://arxiv.org/abs/1408.2051</link>
    <dc:creator>arsyed</dc:creator><description><![CDATA["We extend the work of Narasimhan and Bilmes [30] for minimizing set functions representable as a dierence between submodular functions. Similar to [30], our new algorithms are guaranteed to monotonically reduce the objective function at every step. We empirically and theoretically show that the per-iteration cost of our algorithms is much less than [30], and our algorithms can be used to efficiently minimize a dierence between submodular functions under various combinatorial constraints, a problem not previously addressed. We provide computational bounds and a hardness result on the multiplicative inapproximability of minimizing the dierence between submodular functions. We show, however, that it is possible to give worst-case additive bounds by providing a polynomial time computable lower-bound on the minima. Finally we show how a number of machine learning problems can be modeled as minimizing the dierence between submodular functions. We experimentally show the validity of our algorithms by testing them on the problem of feature selection with submodular cost features."]]></description>
<dc:subject>papers algorithms approximation submodularity</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:4b5cfa9257e2/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:submodularity"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1205.1477">
    <title>[1205.1477] Approximation Algorithms for Online Weighted Rank Function Maximization under Matroid Constraints</title>
    <dc:date>2015-06-22T16:46:33+00:00</dc:date>
    <link>http://arxiv.org/abs/1205.1477</link>
    <dc:creator>arsyed</dc:creator><description><![CDATA[Consider the following online version of the submodular maximization problem under a matroid constraint: We are given a set of elements over which a matroid is defined. The goal is to incrementally choose a subset that remains independent in the matroid over time. At each time, a new weighted rank function of a different matroid (one per time) over the same elements is presented; the algorithm can add a few elements to the incrementally constructed set, and reaps a reward equal to the value of the new weighted rank function on the current set. The goal of the algorithm as it builds this independent set online is to maximize the sum of these (weighted rank) rewards. As in regular online analysis, we compare the rewards of our online algorithm to that of an offline optimum, namely a single independent set of the matroid that maximizes the sum of the weighted rank rewards that arrive over time. This problem is a natural extension of two well-studied streams of earlier work: the first is on online set cover algorithms (in particular for the max coverage version) while the second is on approximately maximizing submodular functions under a matroid constraint. 
In this paper, we present the first randomized online algorithms for this problem with poly-logarithmic competitive ratio. To do this, we employ the LP formulation of a scaled reward version of the problem. Then we extend a weighted-majority type update rule along with uncrossing properties of tight sets in the matroid polytope to find an approximately optimal fractional LP solution. We use the fractional solution values as probabilities for a online randomized rounding algorithm. To show that our rounding produces a sufficiently large reward independent set, we prove and use new covering properties for randomly rounded fractional solutions in the matroid polytope that may be of independent interest.]]></description>
<dc:subject>papers algorithms approximation ranking online submodularity</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:52bfcfa84bfb/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:ranking"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:online"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:submodularity"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://link.springer.com/chapter/10.1007%2FBFb0121195">
    <title>An analysis of approximations for maximizing submodular set functions—II - Springer</title>
    <dc:date>2015-06-22T00:26:00+00:00</dc:date>
    <link>http://link.springer.com/chapter/10.1007%2FBFb0121195</link>
    <dc:creator>arsyed</dc:creator><dc:subject>papers algorithms approximation greedy optimization submodularity</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:10d6f6620ef8/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:greedy"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:submodularity"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://link.springer.com/article/10.1007/BF01588971">
    <title>An analysis of approximations for maximizing submodular set functions—I - Springer</title>
    <dc:date>2015-06-22T00:15:23+00:00</dc:date>
    <link>http://link.springer.com/article/10.1007/BF01588971</link>
    <dc:creator>arsyed</dc:creator><description><![CDATA[LetN be a finite set andz be a real-valued function defined on the set of subsets ofN that satisfies z(S)+z(T)≥z(S⋃T)+z(S⋂T) for allS, T inN. Such a function is called submodular. We consider the problem maxS⊂N{a(S):|S|≤K,z(S) submodular}.
Several hard combinatorial optimization problems can be posed in this framework. For example, the problem of finding a maximum weight independent set in a matroid, when the elements of the matroid are colored and the elements of the independent set can have no more thanK colors, is in this class. The uncapacitated location problem is a special case of this matroid optimization problem.
We analyze greedy and local improvement heuristics and a linear programming relaxation for this problem. Our results are worst case bounds on the quality of the approximations. For example, whenz(S) is nondecreasing andz(0) = 0, we show that a “greedy” heuristic always produces a solution whose value is at least 1 −[(K − 1)/K] K times the optimal value. This bound can be achieved for eachK and has a limiting value of (e − 1)/e, where e is the base of the natural logarithm.]]></description>
<dc:subject>papers algorithms approximation optimization submodularity</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:7090e25b2ffc/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:submodularity"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://jmlr.org/proceedings/papers/v37/leng15.html">
    <title>Hashing for Distributed Data | ICML 2015 | JMLR W&amp;CP</title>
    <dc:date>2015-06-03T20:20:05+00:00</dc:date>
    <link>http://jmlr.org/proceedings/papers/v37/leng15.html</link>
    <dc:creator>arsyed</dc:creator><description><![CDATA[Recently, hashing based approximate nearest neighbors search has attracted much attention. Extensive centralized hashing algorithms have been proposed and achieved promising performance. However, due to the large scale of many applications, the data is often stored or even collected in a distributed manner. Learning hash functions by aggregating all the data into a fusion center is infeasible because of the prohibitively expensive communication and computation overhead. In this paper, we develop a novel hashing model to learn hash functions in a distributed setting. We cast a centralized hashing model as a set of subproblems with consensus constraints. We find these subproblems can be analytically solved in parallel on the distributed compute nodes. Since no training data is transmitted across the nodes in the learning process, the communication cost of our model is independent to the data size. Extensive experiments on several large scale datasets containing up to 100 million samples demonstrate the efficacy of our method.
]]></description>
<dc:subject>papers algorithms hashing knn approximation parallel scaling</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:e274080844c8/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:hashing"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:knn"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:parallel"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:scaling"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.dbs.ifi.lmu.de/~renz/technicalReports/uncertainTimeSeries.pdf">
    <title>Probabilistic Similarity Search for Uncertain Time Series</title>
    <dc:date>2015-02-17T20:39:45+00:00</dc:date>
    <link>http://www.dbs.ifi.lmu.de/~renz/technicalReports/uncertainTimeSeries.pdf</link>
    <dc:creator>arsyed</dc:creator><dc:subject>papers time-series indexing approximation</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:4efb3d325873/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:time-series"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:indexing"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.mit.edu/~mahabadi/sm-thesis.pdf">
    <title>Approximate Nearest Neighbor And Its Many Variants</title>
    <dc:date>2015-02-17T20:12:42+00:00</dc:date>
    <link>http://www.mit.edu/~mahabadi/sm-thesis.pdf</link>
    <dc:creator>arsyed</dc:creator><dc:subject>papers thesis knn approximation algorithms diversity</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:b9e3de1bd5e5/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:thesis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:knn"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:diversity"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1404.1578">
    <title>[1404.1578] Models as Approximations: How Random Predictors and Model Violations Invalidate Classical Inference in Regression</title>
    <dc:date>2015-02-01T18:23:01+00:00</dc:date>
    <link>http://arxiv.org/abs/1404.1578</link>
    <dc:creator>arsyed</dc:creator><description><![CDATA["We review and interpret the early insights of Halbert White who over thirty years ago inaugurated a form of statistical inference for regression models that is asymptotically correct even under "model misspecification," that is, under the assumption that models are approximations rather than generative truths. This form of inference, which is pervasive in econometrics, relies on the "sandwich estimator" of standard error. Whereas linear models theory in statistics assumes models to be true and predictors to be fixed, White's theory permits models to be approximate and predictors to be random. Careful reading of his work shows that the deepest consequences for statistical inference arise from a synergy --- a "conspiracy" --- of nonlinearity and randomness of the predictors which invalidates the ancillarity argument that justifies conditioning on the predictors when they are random. Unlike the standard error of linear models theory, the sandwich estimator provides asymptotically correct inference in the presence of both nonlinearity and heteroskedasticity. An asymptotic comparison of the two types of standard error shows that discrepancies between them can be of arbitrary magnitude. If there exist discrepancies, standard errors from linear models theory are usually too liberal even though occasionally they can be too conservative as well. A valid alternative to the sandwich estimator is provided by the "pairs bootstrap"; in fact, the sandwich estimator can be shown to be a limiting case of the pairs bootstrap. We conclude by giving meaning to regression slopes when the linear model is an approximation rather than a truth. --- In this review we limit ourselves to linear least squares regression, but many qualitative insights hold for most forms of regression."]]></description>
<dc:subject>statistics regression bootstrap misspecification estimation approximation via:cshalizi papers linear-regression</dc:subject>
<dc:identifier>https://pinboard.in/u:arsyed/b:3502ade8b90c/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:regression"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:bootstrap"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:misspecification"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:estimation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:via:cshalizi"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:linear-regression"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.cs.yale.edu/homes/el327/datamining2013a.html">
    <title>Edo Liberty's homepage</title>
    <dc:date>2014-12-30T21:18:54+00:00</dc:date>
    <link>http://www.cs.yale.edu/homes/el327/datamining2013a.html</link>
    <dc:creator>arsyed</dc:creator><dc:subject>data-mining algorithms notes .learn data-stream approximation random-projections</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:26caa142b9b8/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:data-mining"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:notes"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:.learn"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:data-stream"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:random-projections"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.nada.kth.se/~viggo/problemlist/compendium.html">
    <title>A compendium of NP optimization problems</title>
    <dc:date>2014-11-10T22:48:57+00:00</dc:date>
    <link>http://www.nada.kth.se/~viggo/problemlist/compendium.html</link>
    <dc:creator>arsyed</dc:creator><description><![CDATA["catalog of approximability results for NP optimization problems"]]></description>
<dc:subject>ref algorithms approximation</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:9a0e1eefd48a/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:ref"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1110.3767">
    <title>[1110.3767] Anti-sparse coding for approximate nearest neighbor search</title>
    <dc:date>2014-09-30T04:47:46+00:00</dc:date>
    <link>http://arxiv.org/abs/1110.3767</link>
    <dc:creator>arsyed</dc:creator><description><![CDATA["This paper proposes a binarization scheme for vectors of high dimension based on the recent concept of anti-sparse coding, and shows its excellent performance for approximate nearest neighbor search. Unlike other binarization schemes, this framework allows, up to a scaling factor, the explicit reconstruction from the binary representation of the original vector. The paper also shows that random projections which are used in Locality Sensitive Hashing algorithms, are significantly outperformed by regular frames for both synthetic and real data if the number of bits exceeds the vector dimensionality, i.e., when high precision is required."]]></description>
<dc:subject>papers sparsity coding binarization knn approximation lsh indexing qbe .babel</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:6f41f35a5eb0/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:sparsity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:coding"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:binarization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:knn"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:lsh"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:indexing"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:qbe"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:.babel"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://mittheory.wordpress.com/2013/11/22/beyond-lsh/">
    <title>Beyond Locality-Sensitive Hashing – Not so Great Ideas in Theoretical Computer Science</title>
    <dc:date>2014-09-28T21:59:53+00:00</dc:date>
    <link>http://mittheory.wordpress.com/2013/11/22/beyond-lsh/</link>
    <dc:creator>arsyed</dc:creator><dc:subject>hashing lsh knn ann algorithms approximation</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:a577db6998eb/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:hashing"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:lsh"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:knn"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:ann"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://theoryofcomputing.org/articles/v008a014/">
    <title>Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality: Theory of Computing: An Open Access Electronic Journal in Theoretical Computer Science</title>
    <dc:date>2014-09-28T20:29:25+00:00</dc:date>
    <link>http://theoryofcomputing.org/articles/v008a014/</link>
    <dc:creator>arsyed</dc:creator><description><![CDATA["We present two algorithms for the approximate nearest neighbor problem in high-dimensional spaces. For data sets of size n living in ℝd, the algorithms require space that is only polynomial in n and d, while achieving query times that are sub-linear in n and polynomial in d. We also show applications to other high-dimensional geometric problems, such as the approximate minimum spanning tree."]]></description>
<dc:subject>papers algorithms approximation knn ann dimensionality sariel-har-peled piotr-indyk rajeev-motwani</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:7b1c27c17515/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:knn"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:ann"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:dimensionality"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:sariel-har-peled"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:piotr-indyk"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:rajeev-motwani"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1408.3060">
    <title>[1408.3060] Fastfood: Approximate Kernel Expansions in Loglinear Time</title>
    <dc:date>2014-08-17T17:30:56+00:00</dc:date>
    <link>http://arxiv.org/abs/1408.3060</link>
    <dc:creator>arsyed</dc:creator><description><![CDATA["Despite their successes, what makes kernel methods difficult to use in many large scale problems is the fact that storing and computing the decision function is typically expensive, especially at prediction time. In this paper, we overcome this difficulty by proposing Fastfood, an approximation that accelerates such computation significantly. Key to Fastfood is the observation that Hadamard matrices, when combined with diagonal Gaussian matrices, exhibit properties similar to dense Gaussian random matrices. Yet unlike the latter, Hadamard and diagonal matrices are inexpensive to multiply and store. These two matrices can be used in lieu of Gaussian matrices in Random Kitchen Sinks proposed by Rahimi and Recht (2009) and thereby speeding up the computation for a large range of kernel functions. Specifically, Fastfood requires O(n log d) time and O(n) storage to compute n non-linear basis functions in d dimensions, a significant improvement from O(nd) computation and storage, without sacrificing accuracy. 
Our method applies to any translation invariant and any dot-product kernel, such as the popular RBF kernels and polynomial kernels. We prove that the approximation is unbiased and has low variance. Experiments show that we achieve similar accuracy to full kernel expansions and Random Kitchen Sinks while being 100x faster and using 1000x less memory. These improvements, especially in terms of memory usage, make kernel methods more practical for applications that have large training sets and/or require real-time prediction."]]></description>
<dc:subject>kernel-methods papers machine-learning approximation</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:070db067dc89/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:kernel-methods"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:papers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:machine-learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://math.stackexchange.com/questions/38480/how-much-does-symbolic-integration-mean-to-mathematics/">
    <title>How much does symbolic integration mean to mathematics? - Mathematics Stack Exchange</title>
    <dc:date>2014-06-05T18:41:50+00:00</dc:date>
    <link>http://math.stackexchange.com/questions/38480/how-much-does-symbolic-integration-mean-to-mathematics/</link>
    <dc:creator>arsyed</dc:creator><description><![CDATA["The student that worships at the altars of Classical Mathematics should really be warned that his rites frequently have quite oblique connections with the external world." (forman acton)]]></description>
<dc:subject>math numeric integration approximation</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:b2831742f404/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:math"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:numeric"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:integration"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.cs.ucr.edu/~neal/">
    <title>Neal E. Young, Professor - Neal E. Young</title>
    <dc:date>2013-08-09T01:36:55+00:00</dc:date>
    <link>http://www.cs.ucr.edu/~neal/</link>
    <dc:creator>arsyed</dc:creator><dc:subject>people research optimization algorithms approximation</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:0a6ae81dc2f1/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:people"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:research"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://greedyalgs.info/blog/">
    <title>Greedy | and Lagrangian-relaxation algorithms</title>
    <dc:date>2012-11-02T09:24:19+00:00</dc:date>
    <link>http://greedyalgs.info/blog/</link>
    <dc:creator>arsyed</dc:creator><dc:subject>algorithms approximation optimization lagrangian relaxation .read greedy .learn .*</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:1bdbcadfcb37/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:lagrangian"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:relaxation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:.read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:greedy"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:.learn"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:.*"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://matthias.vallentin.net/blog/2011/06/a-garden-variety-of-bloom-filters/">
    <title>A Garden Variety of Bloom Filters (Matthias Vallentin)</title>
    <dc:date>2012-07-02T03:36:08+00:00</dc:date>
    <link>http://matthias.vallentin.net/blog/2011/06/a-garden-variety-of-bloom-filters/</link>
    <dc:creator>arsyed</dc:creator><dc:subject>bloom-filters approximation data-structures via:arthegall</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:3a69c204f9d2/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:bloom-filters"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:data-structures"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:via:arthegall"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.johndcook.com/blog/2011/06/10/stirling-approximation/?">
    <title>Simpler version of Stirling’s approximation (John Cook)</title>
    <dc:date>2011-06-14T20:47:40+00:00</dc:date>
    <link>http://www.johndcook.com/blog/2011/06/10/stirling-approximation/?</link>
    <dc:creator>arsyed</dc:creator><dc:subject>math approximation stirling factorial</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:arsyed/b:455f40acde76/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:math"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:stirling"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:factorial"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.designofapproxalgs.com/">
    <title>The Design of Approximation Algorithms (David P. Williamson and David B. Shmoys)</title>
    <dc:date>2010-11-08T01:03:34+00:00</dc:date>
    <link>http://www.designofapproxalgs.com/</link>
    <dc:creator>arsyed</dc:creator><dc:subject>books algorithms approximation via:shivak</dc:subject>
<dc:identifier>https://pinboard.in/u:arsyed/b:edeeecaae79c/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:books"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:via:shivak"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://dialinf.wordpress.com/2007/12/17/commented-out/">
    <title>A Dialogue on Infinity (Alexandre Borovik)</title>
    <dc:date>2010-09-25T06:53:09+00:00</dc:date>
    <link>http://dialinf.wordpress.com/2007/12/17/commented-out/</link>
    <dc:creator>arsyed</dc:creator><description><![CDATA["Vladimir Arnold forcefully stated in one of his books that it is wrong to think about finite difference equations as approximations of differential equations. It is the differential equation which approximates finite difference laws of physics; it is the result of taking an asymptotic limit at zero. Being an approximation, it is easier to solve and study."
]]></description>
<dc:subject>math physics infinity approximation</dc:subject>
<dc:identifier>https://pinboard.in/u:arsyed/b:a1cb93f7e83f/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:math"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:physics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:infinity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.johndcook.com/blog/2010/08/16/how-to-compute-log-factorial/">
    <title>How to compute log factorial (John Cook)</title>
    <dc:date>2010-08-18T19:01:30+00:00</dc:date>
    <link>http://www.johndcook.com/blog/2010/08/16/how-to-compute-log-factorial/</link>
    <dc:creator>arsyed</dc:creator><description><![CDATA["In summary, one way to compute log factorial is to pre-compute log(n!) for n = 1, 2, 3, … 256 and store the results in an array. For values of n ≤ 256, look up the result from the table. For n > 256, return

(x – 1/2) log(x) – x + (1/2) log(2 π) + 1/(12 x)

with x = n + 1."
]]></description>
<dc:subject>math numeric approximation logarithm factorial</dc:subject>
<dc:identifier>https://pinboard.in/u:arsyed/b:0e3ea837a42a/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:math"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:numeric"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:logarithm"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:factorial"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.johndcook.com/blog/2010/07/27/sine-approximation-for-small-x/">
    <title>Sine approximation for small angles (John Cook)</title>
    <dc:date>2010-07-31T23:41:32+00:00</dc:date>
    <link>http://www.johndcook.com/blog/2010/07/27/sine-approximation-for-small-x/</link>
    <dc:creator>arsyed</dc:creator><description><![CDATA["Not only is the error in sin(θ) ≈ θ approximately θ3/6, it is in fact bounded by θ3/6 for small, positive θ. This comes from the alternating series theorem. When you make an approximation from an alternating Taylor series, the error is bounded by the first term you leave out."
]]></description>
<dc:subject>numeric approximation sin error series math</dc:subject>
<dc:identifier>https://pinboard.in/u:arsyed/b:6d2ac6084434/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:numeric"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:sin"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:error"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:series"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:math"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://pages.cs.wisc.edu/~shuchi/courses/880-S07/">
    <title>Approximation Algorithms Course</title>
    <dc:date>2010-05-20T06:40:16+00:00</dc:date>
    <link>http://pages.cs.wisc.edu/~shuchi/courses/880-S07/</link>
    <dc:creator>arsyed</dc:creator><dc:subject>courses approximation algorithms</dc:subject>
<dc:identifier>https://pinboard.in/u:arsyed/b:cc704e3a028d/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:courses"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:algorithms"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.johndcook.com/blog/2010/04/29/simple-approximation-to-normal-distribution/?utm_source=feedburner&amp;utm_medium=feed&amp;utm_campaign=Feed%3A+TheEndeavour+(The+Endeavour)">
    <title>Simple approximation to normal distribution (John Cook)</title>
    <dc:date>2010-05-09T23:33:35+00:00</dc:date>
    <link>http://www.johndcook.com/blog/2010/04/29/simple-approximation-to-normal-distribution/?utm_source=feedburner&amp;utm_medium=feed&amp;utm_campaign=Feed%3A+TheEndeavour+(The+Endeavour)</link>
    <dc:creator>arsyed</dc:creator><dc:subject>statistics distributions normal cosine approximation</dc:subject>
<dc:identifier>https://pinboard.in/u:arsyed/b:82a67a203807/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:distributions"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:normal"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:cosine"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.johndcook.com/blog/2009/06/29/bancrofts-rule/">
    <title>Incredibly simple approximation (John Cook)</title>
    <dc:date>2009-07-01T03:31:52+00:00</dc:date>
    <link>http://www.johndcook.com/blog/2009/06/29/bancrofts-rule/</link>
    <dc:creator>arsyed</dc:creator><description><![CDATA["You can get a surprisingly good approximation by simply fitting a line to the first and last points. This is known as “Bancroft’s rule.”"
]]></description>
<dc:subject>statistics regression approximation bancrofts-rule</dc:subject>
<dc:identifier>https://pinboard.in/u:arsyed/b:d6b19ec4cdbe/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:regression"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:bancrofts-rule"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.johndcook.com/blog/2009/06/25/probability-approximation/">
    <title>Probability mistake can give a good approximation (John Cook)</title>
    <dc:date>2009-06-29T06:02:37+00:00</dc:date>
    <link>http://www.johndcook.com/blog/2009/06/25/probability-approximation/</link>
    <dc:creator>arsyed</dc:creator><description><![CDATA["When we use np as our approximation, we’re ignoring the terms involving p2 and higher powers of p. When p is small, higher powers of p are very small and can be ignored.  ... Now how small do p and n have to be? If you calculate the approximation np and get a small answer, then it’s a good answer. Why? The error in the np approximation is roughly n(n-1)p2/2, which is less than (np)2. And if np is small, (np)2 is very small."
]]></description>
<dc:subject>probability binomial error approximation</dc:subject>
<dc:identifier>https://pinboard.in/u:arsyed/b:41540acb47e7/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:probability"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:binomial"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:error"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.johndcook.com/blog/2009/02/12/sums-of-uniform-random-values/">
    <title>Sums of uniform random values (John Cook)</title>
    <dc:date>2009-02-14T01:04:54+00:00</dc:date>
    <link>http://www.johndcook.com/blog/2009/02/12/sums-of-uniform-random-values/</link>
    <dc:creator>arsyed</dc:creator><dc:subject>statistics probability distributions normal approximation uniform</dc:subject>
<dc:identifier>https://pinboard.in/u:arsyed/b:05e81f3d278b/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:probability"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:distributions"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:normal"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:uniform"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.johndcook.com/blog/2009/02/10/rolling-dice-for-normal-samples/">
    <title>Rolling dice for normal samples (John Cook)</title>
    <dc:date>2009-02-12T19:37:02+00:00</dc:date>
    <link>http://www.johndcook.com/blog/2009/02/10/rolling-dice-for-normal-samples/</link>
    <dc:creator>arsyed</dc:creator><description><![CDATA["Roll five dice and use the sum to simulate samples from a normal distribution." ... "The variance of a uniform[0,1] random variable is 1/12. So adding 12 together makes the variance 1. That’s why his trick produces a standard random sample."
]]></description>
<dc:subject>probability statistics teaching distributions normal uniform approximation dice random generators</dc:subject>
<dc:identifier>https://pinboard.in/u:arsyed/b:1371a5430d09/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:probability"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:teaching"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:distributions"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:normal"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:uniform"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:dice"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:random"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:generators"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://scienceblogs.com/builtonfacts/2009/02/sunday_function_21.php">
    <title>Sunday Function (Matt Springer)</title>
    <dc:date>2009-02-09T02:07:05+00:00</dc:date>
    <link>http://scienceblogs.com/builtonfacts/2009/02/sunday_function_21.php</link>
    <dc:creator>arsyed</dc:creator><dc:subject>math harmonic series approximation logarithms formulae</dc:subject>
<dc:identifier>https://pinboard.in/u:arsyed/b:8f4d78e6daca/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:math"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:harmonic"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:series"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:logarithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:formulae"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.johndcook.com/relative_error_normal_approx.html">
    <title>Relative error in normal approximations (John Cook)</title>
    <dc:date>2008-11-28T08:12:47+00:00</dc:date>
    <link>http://www.johndcook.com/relative_error_normal_approx.html</link>
    <dc:creator>arsyed</dc:creator><description><![CDATA["This problem of large relative error is not limited to the t distribution but is typical of normal approximations in general. The normal distribution has very thin tails, and in most applications the normal will be used to approximate a distribution with thicker tails. In that case the relative error in the normal approximation will be large in the tails."
]]></description>
<dc:subject>statistics distributions normal approximation relativeError</dc:subject>
<dc:identifier>https://pinboard.in/u:arsyed/b:b5a284a36609/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:distributions"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:normal"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:relativeError"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://geomblog.blogspot.com/2008/07/concept-of-approximation.html">
    <title>The concept of an approximation (Geomblog)</title>
    <dc:date>2008-08-02T08:13:19+00:00</dc:date>
    <link>http://geomblog.blogspot.com/2008/07/concept-of-approximation.html</link>
    <dc:creator>arsyed</dc:creator><description><![CDATA["The real problem with most approximation algorithms is not that the guarantees are too weak or that claimed bounds don't match empirical performance; it's that they suck compared even to easy heuristics, precisely because they're designed for the worst case."
]]></description>
<dc:subject>compsci theory algorithms heuristics np approximation</dc:subject>
<dc:identifier>https://pinboard.in/u:arsyed/b:48268872dfc7/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:compsci"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:heuristics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:np"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://mit.edu/18.098/">
    <title>18.098/6.099. Street Fighting Mathematics</title>
    <dc:date>2008-01-31T05:41:56+00:00</dc:date>
    <link>http://mit.edu/18.098/</link>
    <dc:creator>arsyed</dc:creator><description><![CDATA["The art of guessing results and solving problems without doing a proof
or an exact calculation. Techniques include extreme-cases reasoning,
dimensional analysis, successive approximation, discretization,
generalization, and pictorial analysis. Applica
]]></description>
<dc:subject>math physics approximation course</dc:subject>
<dc:identifier>https://pinboard.in/u:arsyed/b:663e47e7b0c6/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:math"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:physics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:course"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.vendian.org/envelope/dir2/day_of_dots_clock/?do=20:01:39">
    <title>A dot for every second in the day - a clock</title>
    <dc:date>2006-07-05T00:03:18+00:00</dc:date>
    <link>http://www.vendian.org/envelope/dir2/day_of_dots_clock/?do=20:01:39</link>
    <dc:creator>arsyed</dc:creator><dc:subject>dot clock visualization approximation</dc:subject>
<dc:identifier>https://pinboard.in/u:arsyed/b:afefaa34b4d6/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:dot"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:clock"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:visualization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:arsyed/t:approximation"/>
</rdf:Bag></taxo:topics>
</item>
</rdf:RDF>