The Setting
The library derandomizes a randomized space-bounded computation presented as a weighted graph: transition weights that lead from smaller to larger nodes, rewards at the nodes, and acceptance probabilities as the values sought. It does so through a hierarchy of stages, and at every stage an estimator answers requests for the entries of the stage’s matrices and vectors.
The estimator’s randomness comes from fingerprints. Random affine lines over a prime field decide which nodes are retained at each level, and an answer is a table or a vector indexed by an environment of three such lines and by retained nodes. The estimator works in budget blocks: at budget it answers the requests whose cost is small against , from its own answers at smaller budgets, with walks of bounded length on environments in place of averages over all of them. Each request carries an error allowance, and the contract asks, besides sparsity, that every answer lie within the bank, a fixed multiple of its allowance, in a fourth-root norm. The question is whether the answers the estimator actually computes keep this contract at every budget.
Fingerprints and Walks
Let be a prime and , written as a pair of residue pairs.✦ A rank channel over is a pair of a direction in the punctured frame, the set of nonzero vectors of , and an offset ✦; its evaluation at a residue is the point of its line.✦ At a level the box side length is ✦ and the box is , a fraction of .✦ A node , a natural number read modulo , is retained at level by when the hit event occurs: lies in the box, each coordinate taken by its least nonnegative representative.✦ For a finite domain , a finite set of natural numbers, is the set of its nodes retained at level by .✦ The rate of level is .✦
An environment is a triple of rank channels✦, and is the finite average over all environments, the sum of the values divided by their number.✦ For levels , and nodes , , the conditional average at of a function of environments is its average over the environments whose channel retains at level and whose channel retains at level ✦; the conditional average at a node of a function of one channel is its average over the channels that retain the node at a given level.✦
Environments move by walks. A command is a shear, given by a shear choice of two bits, an axial translation, given by a bit, or a cross term, given by two bits✦; a generator is a bit and a command✦, and a generator choice is a generator placed in one of four slots, being the set of generator choices.✦ An atom is a bit and a generator choice, is the set of atoms✦, and a roller index is a letter of the roller alphabet . For levels , and nodes , , a path of atoms and a path of roller indices, words of the same length , move an environment by the roller walk , one roller step per letter✦; the pair is live at when each roller index is the winner for its atom, the roller index selected for that atom at the environment reached so far. The path sampling sum of depth of a function of environments is (1)✦ where is the atom weight.
Stages and Scenes
Matrices and vectors are real and indexed by natural numbers; a product over a finite domain sums the middle index over ✦, and the row weight of a matrix at is .✦ A stochastic step matrix on at rate is a matrix whose entries lie in , whose row weights are at most , and whose positive entries have and ; it is the bounded support matrix on with bound .✦
Parameter constants are natural numbers , , and , an iteration count, two parameters and a number of copies, with (2)✦ where is the cutoff scale, and ; is called admissible when the first two conditions hold. A stage consists of parameter constants, a level, a finite domain and a matrix ✦, and its rate is the rate of its level.✦
A prize triple is a stage with a reward vector and a value vector , the acceptance probability transported to the nodes.✦ A prize triple is correct when the matrix of is a stochastic step matrix on the domain of at the rate of , , every value of lies in , and, with the matrix-vector product over , (3) The iterates of a prize triple are the prize triples obtained from by repeating the prize step, which takes a prize triple to the next one; is the stage of , with domain and matrix , and is the reward vector of .✦
A scene over is a prize triple with natural numbers , , , and : a size bound, a height, a roof, a gap and a walk length.✦ The parameter constants of a scene are those of the stage of its prize triple , and the scene hypotheses on a scene over are that is correct with its stage at level , that and , that for every the domain has at most nodes and is a legal vertex set, a finite set of natural numbers, its nodes all less than , and that the walk length condition holds: (4)✦ where is the ebb factor, is the loss factor of the generator choices at , is the gap constant and is the threshold.
Requests, Norms and Budgets
A row request names a stage , a source level , a destination level , a second destination level , a kind and a main flag .✦ A kind is a chip, a slot for a copy index , an echo with a pilot bit and a round , or a score at round ✦; the echoes are the narrow kinds✦, every kind but a score is paired✦, and is paired main when is set and is paired.✦ A vector request names a stage , a source level and an optional round ✦; a prize request has no round✦, and a detector request has and a round.✦
The axis of is ✦ and that of is .✦ A monotone linear meter on a set is a monotone linear functional on the real functions on ; the fourth moment of under is ✦, and the fourth-root norm is its fourth root.✦ On an axis the vertex meter multiplies by the meter scale the average over environments of the sum over the source domain , retained by the channel of ✦, and the table meter follows it along the sums over the destination domain , retained by the channel .✦ A table family assigns a matrix to each environment✦ and a vertex family a vector✦, and their fourth-root norms under the two meters are the vertex norm and the table norm (5) The table error of two table families and is , with fourth roots taken entrywise.✦
At budget the row request is ready when , , , , and its indices are sane: for a chip, the same with for a slot , and with for an echo or a score at round ✦; here is the padding.✦ The vector request is ready when , , and, if it has a round , and .✦
A step key is a triple of natural numbers✦, and its cost at the gap is . The step key of is ✦ and that of is , with (6)✦ where is the core depth✦, being the lag✦, is for a main request and otherwise, and the depth of a kind is for a chip, for a slot, for an echo with pilot at round , for an echo without pilot at round and for a score at round .✦ A request whose step key has cost is active at budget when ✦, and its error allowance at budget is (7)✦
Targets
The smooth rising ramp from to sends to the value at of the smooth fade function, which sends to with : it vanishes for , equals on and on , and equals for ; for the ramp vanishes up to , increases, and equals from on. The cutoff is minus the ramp from to ✦, the boost is the ramp from to ✦ and the shutoff is minus it✦, the light ramp rises from to ✦, the preparation ramp at rises from to ✦, and the gate at is minus the ramp from to .✦ With ✦, so that is the clamp to ✦, the threshold profile is the shoulder function with threshold and gap ✦, and the inverse clipped denominator is ✦, where is a thousandth of the small constant .✦
The pilot sequence of the stage starts from the zero pilot pair and moves by the stage’s update, its -th pilot pair holding the probed vector and the correction matrix ; the stage correction matrices form the corrected iteration, with and the entrywise correction at the stage’s rate, with weights , of the combined matrix ; and . The question of a row request reads the kind matrix of the stage : the matrix for a chip, the corrected residual for a slot, the test matrix for a score at round or an echo with pilot at round , and the next combined matrix for an echo without pilot at round , products being over .✦ The kind threshold is for a chip or a slot, for an echo and for a score, and the scaled entries of are .✦
A trio of figures is a triple of real functions✦, evaluated at three reals as .✦ The trio of is its main trio ✦: the starting figure is the kind’s piece at levels and when is main, a bin fragment for a chip or a slot, the light ramp for a score and of its argument clipped to for an echo, and otherwise the preparation ramp at ✦; is the inverse clipped denominator when is paired main and otherwise. The support trio at is the ramp from to , minus the ramp from to , and the constant .✦ The switch function at level is , where is the smooth rising ramp from to , the rising cutoff, and is the high cutoff, equal to at level and to at every other level. The directional share of copy at is the share of copy among the copies, equal to for the primary copy and to for every other copy, where is the slice function, the smooth rising ramp from to , so that the shares sum to .
For a finite set , a function on it and a natural number , the padded descending rank is the -th largest value of on , counted with multiplicity, when has more than elements and that value is positive, and otherwise.✦ At an environment the blob of a source lists the scaled entries and, for a paired main request, the companion entries ✦, where the tooth value is the conditional average, over a channel retaining at level and a channel retaining at level , of the bath value of under the two channels.✦ The rank of the blob is .✦ The target table of vanishes at unless , and, when is paired main, , and there (8)✦ the first three factors forming the pre-incoming figure. For an echo the incoming gate is the shutoff of the incoming rank ✦, where the support witness is the support trio evaluated at the same blob without the condition at level ✦, and is the incoming cap limit✦; for a main echo the damping is for the step count , which is with pilot and without.✦ Both factors are in the other cases.
The target of a vector request , its pursued vector, is the same at every environment✦: the rewards for a prize request, and for a detector request at round the test vector of .✦ With the level of and , the averaged score is the conditional average, over the channels retaining at level , of the average over all channels of the rank score .✦ The marked entry weight is the light ramp at times the throttled gate, the gate at of the panel rank of row .✦
The Estimator
A tick assigns to every row request a table family and to every vector request a vertex family ✦, and a roll is a sequence of ticks.✦ Given a roll and a budget , the current tick at is the tick that assigns to every request active at its active table, for a row request, or its active vertex table, for a vector request, and assigns to every other request.✦ The forecast is the current tick at given the roll of the forecasts , followed by empty ticks.✦
Within a block the estimator telescopes along lines. A line is a sequence of table families with an account matrix.✦ At budget the pick of a line at is the walk sample table of the successive difference , the table whose entry at is the path sampling sum (1) of depth for the levels and and the nodes and of the row request being answered, with the remaining slack.✦ The conditional mean table of the difference is the table whose entry at is the conditional average of the difference at , and the sampling fluke is the difference of the pick and the conditional mean table. A flame is a finite set of rays, pairs of natural numbers, each carrying a line, together with a lamp matrix and a base matrix.✦ For a request and a budget , the additive schedule divides into groups, and the prefix sum of a flame at a group is the sum, over the rays of the flame, of the picks of the ray’s line below the start of that group, together with the base matrix from the second group on.
The active vertex table of a vector request is the clamp to of the diagonal of the prefix sum over all groups of its weave, a flame whose lines are built from the roll, taken on the axis of with its destination level replaced by , at the sources in , and at the other nodes.✦ The active table of a row request is built as its target (8) is, with two changes: the blob of each source is the midpoint blob of a buffer run of the request’s compression spray, which compresses its starting flame and its companion flame, and for a main echo the damping gives way to of the running maximum, over the rounds below the step count, of the detector answers in at the environment with and exchanged.✦
Tonic Bounds and the Purse
A function is -Lipschitz when for all reals and .✦ A real function is a bounded fragment with constant when , , its fourth root is at most and -Lipschitz, and for every , where is the symmetric saturation.✦ A trio has test shape at threshold with constant when , and are bounded fragments with constant , vanishes on , and vanishes on and equals on .✦
Tonic bounds for parameter constants are a real such that the fourth roots of the boost, of and of the shutoff are -Lipschitz, the support trio of every kind has test shape at the kind threshold with constant , and so does every main trio of a kind, with its piece at levels and for or the preparation ramp at , and the inverse clipped denominator or .✦ Tonic bounds have the size , the natural size ✦, the bank ✦, the ticket ✦ and the clergy ✦, where is the width.✦
A budget purse for tonic bounds is a triple of reals, a ceiling , a slip and a toll , with (9)✦ The purse meets the purse requirement at a gap when the following holds, with the purse prize , the purse venture , the run charge , the spray price in the last factor of and the droplet count : (10)✦
The Claim
Theorem 1 (Error bounds for the actual estimators). Let be a prime and take a scene over that satisfies the scene hypotheses, with gap . Let be tonic bounds for its parameter constants, with width and bank , and let be a budget purse for them that meets the purse requirement (10) at . Then for every budget the forecast is a trusted tick, a tick whose answers to ready requests satisfy the conditions stated next. For every row request ready at budget , the table family is a tile: its entries are nonnegative with fourth roots at most , the root cap, they are nonzero only at sources in and destinations in , and each row has at most nonzero entries. For an echo each column of also has at most nonzero entries, a sparse shelf, and for a paired main request is pinned at level , unchanged by the terminal mask that clears the destinations outside . For every vector request ready at budget , every value of lies in .✦ Finally, in the norms of the axes of and and with the allowances (7) of their step keys, (11)✦
In the paper, in its own symbols, the result reads: for every allowed task with precision , the actual row outputs, pre-incoming scores and support witnesses satisfy , the clipped vectors have the corresponding ordinary bound, and every allowed reward query satisfies with , uniformly in the task parameters and the stage, with constants independent of the input and of the budget .
What Is Checked
The claim is stated over a scene over a prime with the scene hypotheses, tonic bounds for its parameter constants, a budget purse meeting the purse requirement at the gap, and the forecasts of the estimator, set against the target tables and pursued vectors in the norms of the table and vertex meters, with the error allowances of the step keys. The finite average over a finite set is linear and monotone: for functions , on the set and a real number , (12)