text:
# Thought experiments applying from newons thought experiments on frame of references

A train is travelling towards a tunnel at relativistic velocity. The tunnel has two gates on either side that open/close to admit/reject the train. The train is the same length as the tunnel when it at rest in the tunnel's frame of reference. In the tunnel frame, the train is moving so it is contracted and can fully fit inside the tunnel. Thus, the gates are initially closed, open right before the train enters, close while the train is completely inside the tunnel, open right before the train leaves and closes right after the train has completely left.

How would you describe this sequence of events in the frame of reference of the train??

You have set up the pole-and-barn paradox problem correctly, but you forgot one important detail, which helps to clarify the situation. To recap:

• In the tunnel frame, the train is length contracted and can easily fit in the tunnel.
• In the train frame, the tunnel is length contracted and cannot fit in the tunnel.
• In the tunnel frame, the doors open/close simultaneously.

However, if the tunnel observer sees the train pass through without hitting the doors, that must be true - either it hit the doors, or it didn't. So the only other option is the events (doors opening and closing) are not simultaneous in the train's frame of reference. The train observer sees the back door open, then the front door open, with sufficient time between those events such that the train can pass through the tunnel. Then, the back door closes, and the front door closes once the train has left.

There's a great video about it here.

Also, in case you're wondering, the mathematics of Lorentz contraction are determined by

$$L' = L\sqrt{1-\frac{v^2}{c^2}},$$

where $L$ is the rest length and $L'$ is contracted length. Since in this case, the reference frames are effectively arbitrary, both the tunnel and train frames have equally correct observations.

• Are you saying the observations are the same? – TripleA Dec 31 '16 at 2:37
• No, the train observer and tunnel observer do observe a different order of events, which is the point of the paradox. However, the first postulate of special relativity is that the laws of physics are the same in all inertial reference frames. Both the tunnel and train are in inertial frames. Even though they observe different things, they are both correct in their observations -- it's not like there is a "correct" order of events. – Zack Hutchens Dec 31 '16 at 2:40
• I know but how would you describe the same sequence of events in the frame of reference of the train?? – TripleA Dec 31 '16 at 2:41
• I put that in my answer. I just edited it in bold. See "The train observer sees the back door...". – Zack Hutchens Dec 31 '16 at 2:43

The paradox is resolved because two clocks, each in a different reference frame, measure time at different rates relative to each other, depending on the relative velocities of each reference frame.

For example, if a 50-meter-long train (as measured at rest in the tunnel) travels at 250K meters per second relative to the stationary 50-meter tunnel, then to an observer in the tunnel frame, the train's length would appear to be 50 * sqrt(1-(250K^2 / c^2)) = 27.6 meters, and a 50-meter tunnel would accommodate the train as it passes between simultaneously opening and closing doors.

But to an observer on the train, it would appear that the tunnel rushes past at 250 meters per second, and he would expect that his 50-meter train would not fit into a 27.6-meter tunnel. The doors would be unable to open and close simultaneously without smashing the train. Both observers are making valid observations in their own reference frames.

The key to resolving the paradox may be to visualize that travel time can be a measure of distance, and distance travelled can be a measure of time. In order for the on-board observer and the tunnel observer to agree that the train has passed through the tunnel without smashing into the doors, time measured in the train reference frame must differ from time measured in the tunnel reference frame. From the viewpoint of the on-board observer, the tunnel doors do not open and close simultaneously. This provides time for the rear of the train to enter the tunnel after the front of the train has exited the tunnel. But to the tunnel observer, the doors do open and close simultaneously. Both observers make valid and accurate observations, the train does not smash into the doors, and time is the parameter that absorbs and reconciles the paradox.


text:
Seminars and Colloquia by Series

Friday, October 19, 2018 - 13:05 , Location: Skiles 005 , , CS, Georgia Tech , , Organizer: He Guo
We investigate whether the standard dimensionality reduction techniques inadvertently produce data representations with different fidelity for two different populations. We show on several real-world datasets, PCA has higher reconstruction error on population A than B (for example, women versus men or lower versus higher-educated individuals). This can happen even when the dataset has similar number of samples from A and B . This motivates our study of dimensionality reduction techniques which maintain similar fidelity for A as B . We give an efficient algorithm for finding a projection which is nearly-optimal with respect to this measure, and evaluate it on several datasets. This is a joint work with Uthaipon Tantipongpipat, Jamie Morgenstern, Mohit Singh, and Santosh Vempala.
Friday, October 12, 2018 - 13:05 , Location: Skiles 005 , , ISyE, Georgia Tech , , Organizer: He Guo
Friday, September 28, 2018 - 13:15 , Location: Skiles 005 , , Math, Georgia Tech , , Organizer: He Guo
Given a finite partially ordered set (poset) of width $w$, Dilworth's theorem gives an existence and minimality of a chain partition of size $w$. First-Fit is an online algorithm for creating a chain partition of a poset. Given a linear ordering of the points of the poset, $v_1, \cdots, v_n$, First-Fit assigns the point $v_i$ to the first available chain in the chain partition of the points $v_1, \cdots, v_{i-1}$. It is a known fact that First-Fit has unbounded performance over the family of finite posets of width 2. We give a complete characterization of the family of finite posets in which First-Fit performs with subexponential efficiency in terms of width. We will also review what is currently known on the family of posets in which First-Fit performs with polynomial efficiency in terms of width. Joint work with Kevin Milans.
Friday, September 21, 2018 - 13:05 , Location: Skiles 005 , , CS, Georgia Tech , , Organizer: He Guo
As a generalization of many classic problems in combinatorial optimization, submodular optimization has found a wide range of applications in machine learning (e.g., in feature engineering and active learning).  For many large-scale optimization problems, we are often concerned with the adaptivity complexity of an algorithm, which quantifies the number of sequential rounds where polynomially-many independent function evaluations can be executed in parallel.  While low adaptivity is ideal, it is not sufficient for a (distributed) algorithm to be efficient, since in many practical applications of submodular optimization the number of function evaluations becomes prohibitively expensive.  Motivated by such applications, we study the adaptivity and query complexity of adaptive submodular optimization. Our main result is a distributed algorithm for maximizing a monotone submodular function with cardinality constraint $k$ that achieves a $(1-1/e-\varepsilon)$-approximation in expectation.  Furthermore, this algorithm runs in $O(\log(n))$ adaptive rounds and makes $O(n)$ calls to the function evaluation oracle in expectation.  All three of these guarantees are optimal, and the query complexity is substantially less than in previous works.  Finally, to show the generality of our simple algorithm and techniques, we extend our results to the submodular cover problem. Joint work with Vahab Mirrokni and Morteza Zadimoghaddam (arXiv:1807.07889).
Friday, September 14, 2018 - 13:05 , Location: Skiles 005 , , CS, Georgia Tech , , Organizer: He Guo
We study the dynamic graph connectivity problem in the massively parallel computation model. We give a data structure for maintaining a dynamic undirected graph that handles batches of updates and connectivity queries in constant rounds, as long as the queries fit on a single machine. This assumption corresponds to the gradual buildup of databases over time from sources such as log files and user interactions. Our techniques combine a distributed data structure for Euler Tour (ET) trees, a structural theorem about rapidly contracting graphs via sampling n^{\epsilon} random neighbors, as well as modifications to sketching based dynamic connectivity data structures. Joint work with David Durfee, Janardhan Kulkarni, Richard Peng and Xiaorui Sun.
Friday, April 20, 2018 - 13:05 , Location: Skiles 005 , , CSE, University of Washington , , Organizer: He Guo
We study the $A$-optimal design problem where we are given vectors $v_1,\ldots, v_n\in \R^d$, an integer $k\geq d$, and the goal is to select a set $S$ of $k$ vectors that minimizes the trace of $\left(\sum_{i\in S} v_i v_i^{\top}\right)^{-1}$. Traditionally, the problem is an instance of optimal design of experiments in statistics (\cite{pukelsheim2006optimal}) where each vector corresponds to a linear measurement of an unknown vector and the goal is to pick $k$ of them that minimize the average variance of the error in the maximum likelihood estimate of the vector being measured. The problem also finds applications in sensor placement in wireless networks~(\cite{joshi2009sensor}), sparse least squares regression~(\cite{BoutsidisDM11}), feature selection for $k$-means clustering~(\cite{boutsidis2013deterministic}), and matrix approximation~(\cite{de2007subset,de2011note,avron2013faster}). In this paper, we introduce \emph{proportional volume sampling} to obtain improved approximation algorithms for $A$-optimal design.Given a matrix, proportional volume sampling involves picking a set of columns $S$ of size $k$ with probability proportional to $\mu(S)$ times $\det(\sum_{i \in S}v_i v_i^\top)$ for some measure $\mu$. Our main result is to show the approximability of the $A$-optimal design problem can be reduced to \emph{approximate} independence properties of the measure $\mu$. We appeal to hard-core distributions as candidate distributions $\mu$ that allow us to obtain improved approximation algorithms for the $A$-optimal design. Our results include a $d$-approximation when $k=d$, an $(1+\epsilon)$-approximation when $k=\Omega\left(\frac{d}{\epsilon}+\frac{1}{\epsilon^2}\log\frac{1}{\epsilon}\right)$ and $\frac{k}{k-d+1}$-approximation when repetitions of vectors are allowed in the solution. We also consider generalization of the problem for $k\leq d$ and obtain a $k$-approximation. The last result also implies a restricted invertibility principle for the harmonic mean of singular values.We also show that the $A$-optimal design problem is$\NP$-hard to approximate within a fixed constant when $k=d$.
Physical sensors (thermal, light, motion, etc.) are becoming ubiquitous and offer important benefits to society. However, allowing sensors into our private spaces has resulted in considerable privacy concerns. Differential privacy has been developed to help alleviate these privacy concerns. In this talk, we’ll develop and define a framework for releasing physical data that preserves both utility and provides privacy. Our notion of closeness of physical data will be defined via the Earth Mover Distance and we’ll discuss the implications of this choice. Physical data, such as temperature distributions, are often only accessible to us via a linear transformation of the data.  We’ll analyse the implications of our privacy definition for linear inverse problems, focusing on those that are traditionally considered to be "ill-conditioned”. We’ll then instantiate our framework with the heat kernel on graphs and discuss how the privacy parameter relates to the connectivity of the graph. Our work indicates that it is possible to produce locally private sensor measurements that both keep the exact locations of the heat sources private and permit recovery of the general geographic vicinity'' of the sources. Joint work with Anna C. Gilbert.

format: plain


text:
One More Program and I'm Out!

Given a positive integer nesting level n and string s of printable ascii characters( to ~, output a program which, when run in the same language, outputs a program which outputs a program . . . which outputs the string s.

A total of n programs should be generated, all of which should be run in the same language as your answer.

Note: you may output programs or functions -- anything you are allowed by default as a submission.

You may input s with escaped characters, how a program or function in your language would usually input a string.

Example

For example, given n=1 and s="recursion", a Python 2 program might output:

print "recursion"

Running this would output:

recursion

Given n=2 and s="PPCG", a Python 2 program might output:

print "print \"PPCG\" "

Running this outputs:

print "PPCG"

Running this outputs:

PPCG

Related (+title inspiration): One more LUL and I'm out

Also Related (in sandbox - now deleted, but can still be viewed with enough reputation): Source Code Recursion

Test Cases

Make sure that your code works for the following test cases (one per line):

n s
2 PPCG
4 Robert'); DROP TABLE Students;--
17 Deep
2 Spaces In Here
3 "Don't forget quotes!"
5 'Backtcks might be a htch'
6 5%s
8 [Brackets]<Are>(Great){Usually}

f=->n,s{"$><<%p"%(n>1?f[n-1,s]:s)}  Try it online! R, 62 bytes f=function(n,s){"if"(n,{formals(f)$n=n-1;formals(f)$s=s;f},s)}  Try it online! Call it like so: f(n,s) followed by n copies of () A named function; returns an anonymous function. All it does is modify the default values of the formals of f, allowing the resulting function to be called (and then the result of that called, n times). when n reaches 0, it returns s. R is actually not too bad at escaping! It uses C-style escaping, so you just have to take the input, replace " with \" and \ with \\, and then wrap the whole thing in " ". Underload, 11 bytes (a(S)*)~^^S  Try it online! Input needs to start on the stack, with the number on top in the form of a church numeral. I don't know if this is a valid input method, but the specification has no input, and placing input to the top of the stack seems like a stranded method used in such languages. APL (Dyalog), 24 23 bytes -1 thanks to ngn. This is a full program which prompts for s and then for n and prints to STDOUT. ''''{⍺,⍨⍺,⍵/⍨1+⍵=⍺}⍣⎕⊢⍞  Try it online! (the 17 Deep case is omitted as it exceeds TIO's output limit – works offline) ⍞ prompt for s ⊢ yield that (to separate ⎕ and ⍞) ''''{}⍣⎕ prompt for n and apply this lambda with a single quote as left argument that many times. ⍺ stands for the left argument (the quote) and ⍵ is stands for the right argument (the input text): ⍵=⍺ Boolean where the text is equal to a quote 1+ add one ⍵/⍨ replicate each character of the argument the corresponding number of times ⍺, prepend a quote ⍺,⍨ append a quote This works because strings in APL are ' delimited and single-quotes in strings are doubled, while no other characters need escaping. Dyalog APL also ships with a utility (⎕SE.Dyalog.Utils.repObj) that generates an APL expression which evaluates to its argument (similar to Jelly's uneval). The following program is therefore equivalent to the above, but works for all arrays: ⎕SE.Dyalog.Utils.repObj⍣⎕⊢⎕  Try it online! • I think APLX allows "doubly-" as well as 'singly-quoted' strings. If the rest works there, you can save a byte :) ngn/apl used to but I removed "" recently – ngn Sep 30 '17 at 10:10 • Consider passing the quote as ⍺.- that saves (at least) a byte. – ngn Sep 30 '17 at 10:16 • @ngn Thanks, but APLX doesn't have dfns. NARS2000 has both double-quotes and and dfns, but characters cost two bytes each. – Adám Oct 2 '17 at 7:30 QuadR, 8 bytes Simple translation of ngn's answer. Takes n as argument and s as Input. ^|'|$
'&

Try it online!

PCRE Replace all instances of

^|'|$ Beginning of line OR Quote OR End of line '& with a Quote and the entire match The Argument specifies how many times to repeat the transformation. • ah, now I know what that language is for :) – ngn Oct 2 '17 at 17:47 APL (Dyalog Classic), 19 bytes '^|''|$'⎕r'''&'⍣⎕⊢⍞

Try it online!

• That's very clever. I tried this approach, but didn't think of prepending. – Adám Oct 2 '17 at 7:09
• Sell also this. – Adám Oct 2 '17 at 7:17

As of when I write this, this is the shortest answer for a non-golfing-specific language.

It is a function which takes s and n in that order, and returns the result or the source code of an expression which, when evaluated, returns the next source code.

(!!).iterate show

Argument for why this counts:

1. Solutions are allowed to be functions.
2. Their outputs are allowed to be functions.
3. Those functions have no parameters.
4. In Haskell, since it is lazy and everything-is-curried, the most natural — for practical programming purposes — definition of a 0-parameter function is the same as its result; the closest alternative, a 1-parameter function which ignores the parameter, is silly.

If f is given PPCG and 2 as its parameters, the result is the text "\"PPCG\"" (first generated function), which when evaluated returns the text "PPCG" (second generated funtion), and when that is evaluated it returns PPCG.

Thanks to nimi for suggesting a shortening.

• There is a relevant Meta question on the issue of functions with no arguments in Haskell, though it hasn't received that much attention yet and still has open questions: codegolf.meta.stackexchange.com/q/12924/56433 – Laikoni Sep 29 '17 at 6:48

JavaScript (ES6), 47 44 bytes

Saved 3 bytes thanks to @HermanLauenstein

Takes input in currying syntax (n)(s).

n=>g=s=>alert(atob("${btoa(--n?g(s):s)}"))  Example f(2)('PPCG')  Will output: 'alert(atob("YWxlcnQoYXRvYigiVUZCRFJ3PT0iKSk="))'  Which will print: 'alert(atob("UFBDRw=="))'  Which will print: 'PPCG'  Demo A more complex example where alert() has been overridden so that intermediate results are printed to the console and automatically executed. let f = n=>g=s=>alert(atob("${btoa(--n?g(s):s)}"))

alert = s => { console.log(s); try { eval(s); } catch(e) {} }

alert(f(5)("'Backtcks might be a htch'"));

Alternate version, 40 bytes

Suggested by @Shaggy

This one returns an anonymous function instead of a full program.

n=>g=s=>_=>atob("${btoa(--n?g(s):s)}")  • Could you return an anonymous function, instead of using the alert? 41 bytes – Shaggy Sep 28 '17 at 9:00 • @Shaggy I don't really know. I've asked the OP. – Arnauld Sep 28 '17 at 9:08 • If not, maybe you could get away with an IIFE instead for 45 bytes. – Shaggy Sep 28 '17 at 9:09 • -3 bytes using currying: n=>g=s=>BTalert(atob("${btoa(--n?g(s):s)}"))BT (replace BT with backticks) – Herman L Sep 28 '17 at 17:41
• @HermanLauenstein Thanks! :) – Arnauld Sep 28 '17 at 17:55

Java 8, 95 93 bytes

String c(String s,int n){return"v->\""+(n-->1?c(s,n).replaceAll("[\\\\\"]","\\\$0"):s)+'"';}  -2 bytes thanks to @Lynn. Escaping special characters is so annoying in Java.. Explanation: String c(String s,int n){ // Method with String and int parameters and String return-type return"v->\""+ // Return literal "v->" + a leading double-quote + (n-->1? // If n is larger than 1: c(s,n) // Recursive-call, .replaceAll("[\\\\\"]","\\\$0")
//    with all double-quotes ('"') and slashes ('\') escaped
:                      //   Else:
s)                    //    The input String
+'"';                   //   + a trailing double quote
}                          // End of method

Additional explanation for the regex replacement:

Jelly, 2 bytes

Ṿ¡

Try it online!

Ṿ¡  Main link; left argument (text) is x, right argument (repetitions) is y
¡  Repeat y times:
Ṿ   Uneval x; produce code that outputs x

hehe builtins

• This is broken, "hi" produces hi, not "hi" – Tahg Sep 28 '17 at 0:41
• @Tahg Jelly input is automatically evaluated as Python code if it doesn't throw an error. If it does, then it's just a string. You'd have to do '"hi"' to see the expected outcome – HyperNeutrino Sep 28 '17 at 0:42


text:
# dgl.distributed.sample_etype_neighbors¶

dgl.distributed.sample_etype_neighbors(g, nodes, etype_field, fanout, edge_dir='in', prob=None, replace=False, etype_sorted=True)[source]

Sample from the neighbors of the given nodes from a distributed graph.

For each node, a number of inbound (or outbound when edge_dir == 'out') edges will be randomly chosen. The returned graph will contain all the nodes in the original graph, but only the sampled edges.

Node/edge features are not preserved. The original IDs of the sampled edges are stored as the dgl.EID feature in the returned graph.

This function assumes the input is a homogeneous DGLGraph with the TRUE edge type information stored as the edge data in etype_field. The sampled subgraph is also stored in the homogeneous graph format. That is, all nodes and edges are assigned with unique IDs (in contrast, we typically use a type name and a node/edge ID to identify a node or an edge in DGLGraph). We refer to this type of IDs as homogeneous ID. Users can use dgl.distributed.GraphPartitionBook.map_to_per_ntype() and dgl.distributed.GraphPartitionBook.map_to_per_etype() to identify their node/edge types and node/edge IDs of that type.

Parameters
• g (DistGraph) – The distributed graph..

• nodes (tensor or dict) – Node IDs to sample neighbors from. If it’s a dict, it should contain only one key-value pair to make this API consistent with dgl.sampling.sample_neighbors.

• etype_field (string) – The field in g.edata storing the edge type.

• fanout (int or dict[etype, int]) –

The number of edges to be sampled for each node per edge type. If an integer is given, DGL assumes that the same fanout is applied to every edge type.

If -1 is given, all of the neighbors will be selected.

• edge_dir (str, optional) –

Determines whether to sample inbound or outbound edges.

Can take either in for inbound edges or out for outbound edges.

• prob (str, optional) –

Feature name used as the (unnormalized) probabilities associated with each neighboring edge of a node. The feature must have only one element for each edge.

The features must be non-negative floats, and the sum of the features of inbound/outbound edges for every node must be positive (though they don’t have to sum up to one). Otherwise, the result will be undefined.

• replace (bool, optional) –

If True, sample with replacement.

When sampling with replacement, the sampled subgraph could have parallel edges.

For sampling without replacement, if fanout > the number of neighbors, all the neighbors are sampled. If fanout == -1, all neighbors are collected.

• etype_sorted (bool, optional) – Indicates whether etypes are sorted.

Returns

A sampled subgraph containing only the sampled neighboring edges. It is on CPU.

Return type

DGLGraph


text:
Limits of inverse Trigonometric functions

There are two useful inverse trigonometric limit rules in calculus. Firstly, learn the limit properties and you will know how limits of inverse trigonometric functions are used for dealing inverse trigonometric functions in calculus.

$(1) \,\,\,\,\,\,$ $\displaystyle \large \lim_{x \,\to\, 0}{\normalsize \dfrac{\sin^{-1}{x}}{x}} \,=\, 1$

$(2) \,\,\,\,\,\,$ $\displaystyle \large \lim_{x \,\to\, 0}{\normalsize \dfrac{\tan^{-1}{x}}{x}} \,=\, 1$

Email subscription
Math Doubts is a best place to learn mathematics and from basics to advanced scientific level for students, teachers and researchers. Know more
Follow us on Social Media
Math Problems

Learn how to solve easy to difficult mathematics problems of all topics in various methods with step by step process and also maths questions for practising.


text:
# 180 Days of Math for Fifth Grade Day 5 Answers Key

By accessing our 180 Days of Math for Fifth Grade Answers Key Day 5 regularly, students can get better problem-solving skills.

## 180 Days of Math for Fifth Grade Answers Key Day 5

Directions Solve each problem.

Question 1.
29 + 7 = ___
Answer:
Perform an addition operation to find the sum of the two given numbers.
29 + 7 = 36

Question 2.

Answer: 35
By performing the multiplication operation for the two given numbers we can find the product of 5 and 7.
Multiplying 5 by 7 we get 35.

Question 3.
28 ÷ 4 = ___
Answer: 7
By performing the division operation for the two given numbers we can find the quotient of 28 and 7.
Dividing 28 and 4 we get the quotient as 7.

Question 4.
How many digits are in 29,400?
_______________
Answer: There are 5 digits in 29,400.

Question 5.
Is $$\frac{5}{6}$$ greater than, less than, or equal to $$\frac{10}{12}$$ ?
______________________
Answer:
5/6 is equal to 10/12
As both the nominator and denominator are divisible by 2.

Question 6.
Write the number that comes next in the sequence.
667, 767, 867, _______
Answer: 667, 767, 867, 967.

Question 7.
25 ÷ 5 = 5 ×
Answer: 25 ÷ 5 = 5 x 5

Question 8.
Do you use A.M. or P.M. to write 3:29 in the morning?
_______________
Answer: 3:29 AM we use in the morning time.

Question 9.
Is the angle obtuse, acute, or right?
______________________

Answer: It is Acute angle as it measures less than 90 degrees.

Question 10.
Record the following data in the chart using tally marks.
The Hill family has 4 cats and 2 dogs.
The Diaz family has 2 dogs and no cats.

 Dogs Cats Hill family Diaz family

Answer:

 Dogs Cats Hill family |||| || Diaz family ||

Question 11.
Imagine that you write each letter of the word IMAGINE on individual cards. You shuffle them, turn them facedown on a table, and turn over the top card. What is the probability of turning over an A?
____________________
Answer:
There are 7 letters in the word imagine,
And there is only one A in it,
Therefore, the probability of A is 1/7.

Question 12.
My product is 30. The difference of the two factors is 1. The sum of the two factors is 11. What numbers am I?
________________
Answer:
As when we multiply 5 with 6 we get 30,
By subtracting 5 from 6 we get 1,
By adding 5 with 6 we get 11.

Scroll to Top


text:
# Multiple unattended prints using extruder to sweep build plate?

I read something the other day about a guy who found a way to knock over completed prints with the printer head itself, then slide them to the edge of the build plate, where they fall into a box/basket. This allows printing several Eiffel Towers while you sleep for example. It doesn't work with skirts (duh), and the adhesion has to be just right not to wake up with a pile of spaghetti, but it still sounds useful.

Well, now I cannot re-find the description I read; does anyone know what this process is called? Is there an easy way I can perform such an end-of-print action on my CR-10 with a cura plugin? If such a thing takes a touch of end-time custom gcode, is there a proof of concept rough draft or demo I can start tinkering with? Any more info is helpful.

• Welcome to 3D Printing.SE! It will probably not work with brims either. The process is called series production. – 0scar Jul 12 '18 at 9:02
• – Greenonline Jul 12 '18 at 11:01
• And for fun, from Thingiverse - Automatic Print Ejector - The Punching Machine. There's even a video: MatterHackers Punch-Out! – Greenonline Jul 12 '18 at 11:04
• @Greenonline: thanks. I checked those out to see if they had this technique covered, but the one I saw/lost needed no extra parts or mods, which is what excited me most about it... – dandavis Jul 12 '18 at 18:03
• If you could relocate the link that you first saw, that would be great – Greenonline Jul 13 '18 at 10:43

You could cool down the heated bed (with e.g. [M109][1] R28) and cool down the hotend (with e.g. [M190][1] R40). This will usually release the print from the plate, perform the actions to move the head (e.g. go to the largest X, Y position G1 X{max} Y{max}, move down G1 Z10 to then move to minimum X, Y G1 X0 Y0 position such that it sweeps the print to the origin) that it knocks it into the basket and start printing again by copy pasting the whole G-code beforehand a couple of times. Note that this all depends on the product you are printing. You should at least use the end code scripts for the specific tasks to cool down, and start scripts to heat up again.

You can write a Cura plugin to implement a new GUI item to copy the G-code multiple times or create a post processing plugin.

• I was planning to use cura or repetier host's end/start snip sections, with AutoIt to re-print when done. Sounds like I need to learn about gcode commands and the few above will cover me. It takes per-print setup and hard-to-perform testing but should be workable. I was secretly hoping that someone would know the article I saw, link to it, and it would have a low-effort plugin or example gcode, but you make it seem pretty simple... – dandavis Jul 12 '18 at 18:41

I would advice against it, or at least have some detection for when the object won't budge:

Leaving a printer unattended needs special care too (fire alarm springs to mind but not only).

• Agreed -- using the print head as a wedge/driver is far worse than those homeowners who use a screwdriver as a can-opener. – Carl Witthoft Jul 12 '18 at 12:21
• This is caused by the horrible build platform. With a glass bed like the Ultrabase this wouldn't happen. Good point about the fire alarm. – AndreKR Jul 12 '18 at 15:57
• @CarlWitthoft - More like those home owners who check the electrical output of a wall socket with said screwdriver ... – Pᴀᴜʟsᴛᴇʀ2 Jul 12 '18 at 17:34
• Good point about monitoring, something I will take into consideration for sure. w/adhesion, I don't use tape anymore (glass+hairspray only), and can adjust 1st layer temp and whatnot to get it barely cling through the printing. Applicability depends on the print I suppose: a maker coin would be much harder than the almost-ideal Eiffel Tower... – dandavis Jul 12 '18 at 18:09
• @dandavis You can do multiple coins on the build plate at once or sequentially, unless they are huge coins – 0scar Jul 12 '18 at 18:46


text:
# There are $n!$ different unitary similarities that give $L_i \sim L_j$. Or are there more?

Given a matrix $L$ of dimension $n \times n$ which is lower triangular, and with distinct elements along the diagonal, there is a way to unitarily transform it into a different lower triangular matrix as follows.

With $L$'s lower triangular, $P$'s permutations, $D$'s diagonal, $Q$'s unitary, and $C$'s non-sungular: \begin{align} CL_0C^{-1}&=D_0 \\ PD_0P^*&=D_1 \\ QD_1Q^* &= L_1 \\ \end{align}

The claim is that the total change is a unitary similarity, or equivalently that $L_1 = UL_0 U^*$ for some $U$ unitary.

Begin Placeholder On the likely chance that clarifications of my claim are necessary, I will insert/edit here later. For now a (hopefully complete and clear) sketch.

The matrix is first diagonalized and re-ordered via permutation so that we have : $$D_1=PCL_0C^{-1}P^*$$

The original matrix $L_0$ is now represented in a similar diagonal form with respect to the re-ordered diagonal matrix $D_1$: $$L_0 = C^{-1}\underbrace{P^*D_1P}_{D_0}C$$

From this point, similarity operations may be applied to $D_1$ putting it in lower triangular form. This is done with the goal of the unitary $U$ in mind:

Factor $C^{-1}P^*=UR$ from the QR factorization of $C^{-1}P^*$ where $U$ is unitary. Then $$L_0 = \underbrace{UR}_{C^{-1}P^*}D_1R^{-1}U^*$$

Since $R$ is lower triangular, its inverse is also, and we have $L_1 = RD_1R^{-1}$ is lower triangular. Thus the unitary similarity is shown $$L_0 = UL_1 U^*$$

End Placeholder

This all amounts to re-ordering the diagonal elements of $L_i$ while unitarily retaining the lower triangular structure. Thus since there are $n!$ such possible orderings resulting in distinct $L_i$, there are $n!$ different unitary transformations. So for my question:

Does this enumerate (up to the number of distinct diagonal elements) all such unitary similarities between lower triangular forms?

I don't know the answer to this question. I am very interested in any discussion since differing viewpoints will likely be enlightening.

-
$Q$ and $P$ are unitary. Since the unitary matrices form a group, $QPC$ is unitary if and only if $C$ is unitary.


text:
# Totally bounded and closed implies compact??

Is there a fault in exercice 9.3.1 b) from Analysis by Zorich? The exercice asks to prove that a subset of a metric space is compact if and only if it is totally bounded and closed. But I have a counterexample for it: Consider the open unit ball $$B(0,1)$$ in $$\mathbb{R}^n$$ as a metric space itself. Then it is closed in itself and totally bounded, but not compact.

Am I right?

• " closed in itself " ? – Yadati Kiran Dec 18 '18 at 14:48
• Are you suggesting $B(0,1)$ endowed with subspace topology of $\mathbb{R}^n$ ? – Yadati Kiran Dec 18 '18 at 14:55
• @YadatiKiran yes – Jiu Dec 18 '18 at 14:56
• it is not closed in $\mathbb R^n$ which is presumably what is implied... – Carmeister Dec 18 '18 at 19:15
• @Carmeister but one does not write simply “metric space” and imply that it is $\mathbb{R}^n$. – Jiu Dec 19 '18 at 3:01

You are right.

For a subset $$A$$ of metric space $$(X,d)$$ to be compact, it is not enough that $$A$$ is totally bounded and closed (since $$X$$ is always closed). However, the correct assumptions to conclude that $$A$$ is compact are that it is totally bounded and complete. You can follow the link I included in my previous answer to a similar question to see that proof of this fact.

• Almost certainly, the problem should have been to prove that a subset of a complete metric space is compact iff it is closed and totally bounded. This is true because the subset will then be complete itself if and only if it is closed in $X$. I do not know if Zorich accidently left off the word "complete" in the exercise, or if Jiu just missed it in the context. – Paul Sinclair Dec 18 '18 at 17:10
• @PaulSinclair That's also my understanding as well. Regardless, I decided to answer the question as is presented here since I don't have access to the book soI couldn't check. – BigbearZzz Dec 18 '18 at 17:18
• @PaulSinclair I don’t know how to upload a picture but there was no “complete” in the exercise. I typed the exercise word for word apart from “Show that”. – Jiu Dec 18 '18 at 23:22
• @Jiu - I'll take your word for it. You have to understand that people missing important words in their exercises is a fairly common occurrence here. Sometimes they fail to recognize that the word is important, and sometimes they just read past it. It happens to me, too.. So without access to the book, I did not have a way to verify that the exercise was indeed in error. But if you've double-checked, then I am sure that it is. – Paul Sinclair Dec 18 '18 at 23:58

$$B(0,1)$$ is closed in the space $$B(0,1)$$ endowed with the subspace topology of $$\mathbb{R}^n$$. But this is true for every $$S \subset \mathbb{R}^n$$ if we endow $$S$$ with the subspace topology.

The requirement is that the set is closed in $$\mathbb{R}^n$$, not in itself.

Moreover, in a generic tolopogical space X, given $$A \subset X$$, the equivalence " $$A$$ is compact if and only if closed and totally bounded" is correct in the case the ambient space $$X$$ is complete. In this case every closed subspace of $$X$$ is also complete.

• The requirement in the exercise is that the set is closed in a metric space. Since every subspace of a metric space is a metric space itself, this is an empty requirement. – Jiu Dec 19 '18 at 3:04

Hint: what is the bound on $$B(0,1)$$ in $$B(0,1)$$?

• Are you suggesting that $B(0,1)$ is not totally bounded? – Toby Bartels Dec 18 '18 at 21:47


text:
# Why is the intensity of the IR spectra of IBr higher than that of ICl?

Why is the intensity of the IR spectra of $$\ce{IBr}$$ higher than that of $$\ce{ICl}$$?

I know that the IR spectra intensities are proportional to the derivative of the dipole moment with internuclear distance. However, how would one be able to deduce (without looking at the IR spectra) that the IR spectra for $$\ce{IBr}$$ is higher than $$\ce{ICl}$$ in the gas phase?

I would have thought it would be the other way around since $$\ce{Cl}$$ has the higher electronegativity.


text:
Home OALib Journal OALib PrePrints Submit Ranking News My Lib FAQ About Us Follow Us+
 Title Keywords Abstract Author All
Search Results: 1 - 10 of 100 matches for " "
 Page 1 /100 Display every page 5 10 20 Item
 Computer Science , 2015, Abstract: Linguistic structures exhibit a rich array of global phenomena, however commonly used Markov models are unable to adequately describe these phenomena due to their strong locality assumptions. We propose a novel hierarchical model for structured prediction over sequences and trees which exploits global context by conditioning each generation decision on an unbounded context of prior decisions. This builds on the success of Markov models but without imposing a fixed bound in order to better represent global phenomena. To facilitate learning of this large and unbounded model, we use a hierarchical Pitman-Yor process prior which provides a recursive form of smoothing. We propose prediction algorithms based on A* and Markov Chain Monte Carlo sampling. Empirical results demonstrate the potential of our model compared to baseline finite-context Markov models on part-of-speech tagging and syntactic parsing.
 Online Brazilian Journal of Nursing , 2008, Abstract: We understand that adolescence is a period of several transformations. We objectify in this study to investigate the vulnerability and the risks of adolescents in the midst of ST/HIV/Aids in their several contexts. It was used the exploratory method, and based on a cultural and ethnographical approach, developed in an elementary and high school in Fortaleza, Ceará, in the period between April and June, 2007. The following instruments were used to work with the 20 selected adolescents observation, participant observation, field diary, focal group. The students of this study were divided into two focal groups according to the gender. There were five meetings with the average duration of 90 minutes. For the data analysis, it was used the content analysis of Bardin. As a result, it is possible to emphasize that social groups are essential in adolescents’ formation of knowledge related to STD/HIV/Aids, however there is a deficit of reflexive and constructive dialogue in these spaces, which are not performing their real roles. This problem together with womanly submission, culturally rooted, influences the risk and vulnerability that expose the adolescents. Therefore, it was concluded that the society as a whole needs to reflect on these factors, distinguishing its roles in the control of STD/HIV/Aids of the adolescents as well as of the population in general, aiming health promotion.
 Online Brazilian Journal of Nursing , 2008, Abstract: We understand that adolescence is a period of several transformations. We objectify in this study to investigate the vulnerability and the risks of adolescents in the midst of ST/HIV/Aids in their several contexts. It was used the exploratory method, and based on a cultural and ethnographical approach, developed in an elementary and high school in Fortaleza, Ceará, in the period between April and June, 2007. The following instruments were used to work with the 20 selected adolescents observation, participant observation, field diary, focal group. The students of this study were divided into two focal groups according to the gender. There were five meetings with the average duration of 90 minutes. For the data analysis, it was used the content analysis of Bardin. As a result, it is possible to emphasize that social groups are essential in adolescents’ formation of knowledge related to STD/HIV/Aids, however there is a deficit of reflexive and constructive dialogue in these spaces, which are not performing their real roles. This problem together with womanly submission, culturally rooted, influences the risk and vulnerability that expose the adolescents. Therefore, it was concluded that the society as a whole needs to reflect on these factors, distinguishing its roles in the control of STD/HIV/Aids of the adolescents as well as of the population in general, aiming health promotion.
 Tim Austin Mathematics , 2013, Abstract: Let $(X,\mu)$ be a probability space, $G$ a countable amenable group and $(F_n)_n$ a left F\o lner sequence in $G$. This paper analyzes the non-conventional ergodic averages $\frac{1}{|F_n|}\sum_{g \in F_n}\prod_{i=1}^d (f_i\circ T_1^g\cdots T_i^g)$ associated to a commuting tuple of $\mu$-preserving actions $T_1$, ..., $T_d:G\curvearrowright X$ and $f_1$, ..., $f_d \in L^\infty(\mu)$. We prove that these averages always converge in $\|\cdot\|_2$, and that they witness a multiple recurrence phenomenon when $f_1 = \ldots = f_d = 1_A$ for a non-negligible set $A\subseteq X$. This proves a conjecture of Bergelson, McCutcheon and Zhang. The proof relies on an adaptation from earlier works of the machinery of sated extensions.
 Marcel Erné Mathematics , 2014, Abstract: Morphisms between (formal) contexts are certain pairs of maps, one between objects and one between attributes of the contexts in question. We study several classes of such morphisms and the connections between them. Among other things, we show that the category CLc of complete lattices with complete homomorphisms is (up to a natural isomorphism) a full reflective subcategory of the category of contexts with so-called conceptual morphisms; the reflector associates with each context its concept lattice. On the other hand, we obtain a dual adjunction between CLc and the category of contexts with so-called concept continuous morphisms. Suitable restrictions of the adjoint functors yield a categorical equivalence and a duality between purified contexts and doubly based lattices, and in particular, between reduced contexts and irreducibly bigenerated complete lattices. A central role is played by continuous maps between closure spaces and by adjoint maps between complete lattices.
 Intelligent Information Management (IIM) , 2018, DOI: 10.4236/iim.2018.105010 Abstract: LightGBM is an open-source, distributed and high-performance GB framework built by Microsoft company. LightGBM has some advantages such as fast learning speed, high parallelism efficiency and high-volume data, and so on. Based on the open data set of credit card in Taiwan, five data mining methods, Logistic regression, SVM, neural network, Xgboost and LightGBM, are compared in this paper. The results show that the AUC, F1-Score and the predictive correct ratio of LightGBM are the best, and that of Xgboost is second. It indicates that LightGBM or Xgboost has a good performance in the prediction of categorical response variables and has a good application value in the big data era.
 Mitat Uysal Journal of Applied Sciences , 2006, Abstract: In this study, several radial basis function networks are compared according to their approximation ability in time series forecasting problems. Optimal values for the tested parameters are obtained using computer simulation runs. Effects of width selection in Gaussian Kernels, of the number of neurons in the hidden layer, and of selection of kernel function are investigated.
 Genome Biology , 2006, DOI: 10.1186/gb-2006-7-s1-s8 Abstract: MARS uses the mouse, rat, dog, opossum, chicken, and frog genome sequences as pairwise informant sources for Twinscan and combines the resulting transcript predictions into genes based on coding (CDS) region overlap. Based on the EGASP assessment, MARS is one of the more accurate dual-genome prediction programs. Compared to the GENCODE annotation, we find that predictive sensitivity increases, while specificity decreases, as more informant species are used. MARS correctly predicts alternatively spliced transcripts for 11 of the 236 multi-exon GENCODE genes that are alternatively spliced in the coding region of their transcripts. For these genes a total of 24 correct transcripts are predicted.The MARS algorithm is able to predict alternatively spliced transcripts without the use of expressed sequence information, although the number of loci in which multiple predicted transcripts match multiple alternatively spliced transcripts in the GENCODE annotation is relatively small.Accurate prediction of protein-coding genes in mammals remains a challenging and active area of research [1]. In the past decade the most important advance in de novo gene prediction came with the initial availability of extensive human and mouse genomic sequences. Several gene prediction algorithms were introduced at that time that improved gene prediction by using the specific patterns of evolutionary conservation that are indicative of protein coding genes [2-4].All of the dual-genome (category 4) gene finders participating in EGASP rely on alignments to one or more informant genome sequences. For predicting human genes, dual-genome gene prediction algorithms most often use the mouse genome sequence as a source of evolutionary conservation information. This was originally a consequence of the early availability, with respect to other mammals, of the mouse genome sequence [5-8]. However, as additional genomes were sequenced, it became apparent that the evolutionarily divergence between human and
 PLOS ONE , 2013, DOI: 10.1371/journal.pone.0057310 Abstract: Objective We examined whether a panel of SNPs, systematically selected from genome-wide association studies (GWAS), could improve risk prediction of coronary heart disease (CHD), over-and-above conventional risk factors. These SNPs have already demonstrated reproducible associations with CHD; here we examined their use in long-term risk prediction. Study Design and Setting SNPs identified from meta-analyses of GWAS of CHD were tested in 840 men and women aged 55–75 from the Edinburgh Artery Study, a prospective, population-based study with 15 years of follow-up. Cox proportional hazards models were used to evaluate the addition of SNPs to conventional risk factors in prediction of CHD risk. CHD was classified as myocardial infarction (MI), coronary intervention (angioplasty, or coronary artery bypass surgery), angina and/or unspecified ischaemic heart disease as a cause of death; additional analyses were limited to MI or coronary intervention. Model performance was assessed by changes in discrimination and net reclassification improvement (NRI). Results There were significant improvements with addition of 27 SNPs to conventional risk factors for prediction of CHD (NRI of 54%, P<0.001; C-index 0.671 to 0.740, P = 0.001), as well as MI or coronary intervention, (NRI of 44%, P<0.001; C-index 0.717 to 0.750, P = 0.256). ROC curves showed that addition of SNPs better improved discrimination when the sensitivity of conventional risk factors was low for prediction of MI or coronary intervention. Conclusion There was significant improvement in risk prediction of CHD over 15 years when SNPs identified from GWAS were added to conventional risk factors. This effect may be particularly useful for identifying individuals with a low prognostic index who are in fact at increased risk of disease than indicated by conventional risk factors alone.
 BMC Bioinformatics , 2004, DOI: 10.1186/1471-2105-5-71 Abstract: Nine different small SCFGs were implemented to explore the tradeoffs between model complexity and prediction accuracy. Each model was tested for single sequence structure prediction accuracy on a benchmark set of RNA secondary structures.Four SCFG designs had prediction accuracies near the performance of current energy minimization programs. One of these designs, introduced by Knudsen and Hein in their PFOLD algorithm, has only 21 free parameters and is significantly simpler than the others.Many RNAs conserve a base-paired secondary structure that is important to their function [1,2]. Accurate RNA secondary structure predictions help in understanding an RNA's function, in identifying novel functional RNAs in genome sequences, and in recognizing evolutionarily related RNAs in other organisms. Most RNA secondary structure prediction algorithms are based on energy minimization [2-7]. Alternatively, probabilistic modeling approaches using stochastic context-free grammars (SCFGs) can be used [8-10]. A potential advantage of a probabilistic modeling approach is that it is more readily extended to include other sources of statistical information that constrain a structure prediction.For example, an outstanding problem is consensus RNA secondary structure prediction for a small number of structurally homologous RNA sequences. Comparative sequence analysis is probably the most powerful source of information for RNA structure prediction [11-14]. Homologous RNAs tend to conserve a common base-paired secondary structure, and conserved base-pairing interactions are revealed by compensatory mutations in multiple RNA sequence alignments [12,15-19]. Comparative sequence analysis is extremely reliable, and has produced strikingly accurate RNA structure predictions [14,20], but one is usually not blessed with the large number of sequences (nor the time and human expertise) that a purely comparative approach requires. There is a need for automated approaches that combine evolutionary
 Page 1 /100 Display every page 5 10 20 Item


text:
# statistical arbitrage using PCA

While reading the paper Statistical Arbitrage in the U.S. Equities Market by Marco Avellaneda and Jeong-Hyun Lee on statistical arbitrage using PCA

I realized that the author sums the residuals of regression against PCA factors and says that is mean reverting. By standard regression principles aren't residuals IID normal and hence their sum should be a random walk? Then how can the sum of residuals be mean reverting?

## 1 Answer

The estimation of the parameters by regression ensures that the mean of the residuals is 0. So, technically the residuals are not IID as if the number of observations is $$n$$, any $$n-1$$ residuals completely determine the last one.

In practice, the assumption of iid-ness is not realistic anyway.


text:
## Armature Reaction in Alternator at Lagging Power Factor Load

Manish Kumar Saini

Updated on 25-Sep-2021 07:18:51

Consider a 2-pole alternator as shown in Figure-1. Suppose that the alternator is loaded with an inductive load of zero power factor lagging. In this case, the phase current 𝐼𝑅 , 𝐼𝑌 and 𝐼𝐵 will be lagging with their respective phase voltages 𝐸𝑅 , 𝐸𝑌 and 𝐸𝐵 by 90°. The ... Read More

## Advantages of Stationary Armature–Rotating Field Alternator

Manish Kumar Saini

Updated on 25-Sep-2021 07:13:40

Practically, most of the synchronous generators or alternators have stationary armature and rotating field.A stationary armature-rotating field alternator has several advantages over a rotating armature type alternator, as given below −When a stationary armature is used in the alternator, the output current can be taken directly from the fixed terminals ... Read More

## Synchronous Impedance Method (EMF Method) for Finding Voltage Regulation of Alternator

Manish Kumar Saini

Updated on 25-Sep-2021 07:09:27

The synchronous impedance method or EMF method is used to determine the voltage regulation of the larger alternators. The synchronous impedance method is based on the concept of replacing the effect of armature reaction by an imaginary reactance.For an alternator, \mathrm{𝑽 = 𝑬_{𝒂} − 𝑰_{𝒂}𝒁_{𝒔} = 𝑬_{𝒂} − 𝑰_{𝒂}(𝑅_{𝒂} + ... Read More

## Saturated and Unsaturated Synchronous Reactance in Synchronous Generator

Manish Kumar Saini

Updated on 25-Sep-2021 07:01:17

Unsaturated Synchronous ReactanceAt low excitations, the open-circuit characteristic (OCC) of an alternator coincides with the air-gap line, thus, the synchronous impedance of the alternator is constant and this value of the synchronous impedance is known as linear or unsaturated synchronous impedance.The unsaturated synchronous reactance (denoted by Xsu) can be obtained ... Read More

## What is Synchronous Reactance & Synchronous Impedance?

Manish Kumar Saini

Updated on 25-Sep-2021 06:55:58

In an alternator or synchronous generator, the actual generated voltage consists of the summation of two component voltages. One of these component voltages is the excitation voltage  (𝐸exc); it is the voltage that would be generated because of the field excitation only. The excitation voltage is the voltage that would ... Read More

## Significance of Short Circuit Ratio of Alternator (Synchronous Machine)

Manish Kumar Saini

Updated on 25-Sep-2021 06:53:12

In a synchronous machine, the short-circuit ratio (SCR) is an important factor. The SCR affects the physical size, operating characteristics and cost of the synchronous machine.Low Value of SCRWith a low value of SCR, the synchronous machine is very sensitive to the load variations, i.e., the alternator has a large ... Read More

## What is Hunting Effect in Alternator?

Manish Kumar Saini

Updated on 25-Sep-2021 06:50:59

What is Hunting in Alternator?When an alternator or synchronous generator is running under normal condition, the armature field and the rotor magnetic field will be rotating in the same direction at synchronous speed.When either a sudden change in the load of the alternator or a change in the torque of ... Read More

## Torque-Pulse Rate Characteristics of a Stepper Motor

Manish Kumar Saini

Updated on 24-Sep-2021 07:37:31

The torque-pulse rate characteristics of a stepper motor is the graph plotted between the electromagnetic torque and the stepping rate. It gives the variation of electromagnetic torque as a function of stepping rate in pulses per second (pps). A stepper motor is usually described by two characteristic curves as shown ... Read More

## No-Load Test and Blocked-Rotor Test on Single-phase Induction Motor

Manish Kumar Saini

Updated on 24-Sep-2021 06:52:07

The equivalent circuit parameters of a single-phase induction motor can be determined from the blocked rotor and no-load tests. Except, the capacitor-run motor, the blocked rotor and no-load tests are performed with auxiliary winding kept open.Blocked Rotor Test on Single-phase Induction MotorIn the blocked rotor test, the rotor of the ... Read More

## Methods of Starting Single-phase Induction Motor

Manish Kumar Saini

Updated on 24-Sep-2021 06:28:37

Why doesn't a Single-Phase Induction Motor Self-Start?A single-phase induction motor consists of a squirrel cage rotor and a stator carrying a single-phase winding. But, a single-phase induction motor is not self-starting like a 3-phase induction motor since it requires some starting means.When a single-phase supply is fed to the stator ... Read More


text:
# Find the equation of the tangents to the circle ${{x}^{2}}+{{y}^{2}}=4$ which are perpendicular to the line $12x-5y+9=0$ . Also find the points of contact.

Verified
146.7k+ views
Hint: We first need to write the equation of the line given in $y=mx+c$ the form. Then we know that the product of slopes of two perpendicular lines is -1. Therefore, ${{m}_{1}}.{{m}_{2}}=-1$ .To find the value of the c, we can use the formula for perpendicular distance (d) of a line $Ax+By+C=0$ from a point $O\left( {{x}_{1}},{{y}_{1}} \right)$ is given by, $d=\dfrac{\left| A{{x}_{1}}+B{{y}_{1}}+C \right|}{\sqrt{{{A}^{2}}+{{B}^{2}}}}$ .

Let’s analyze the circle first. We have given the equation of the circle as ${{x}^{2}}+{{y}^{2}}=4$
Comparing with the equation, ${{\left( x-a \right)}^{2}}+{{\left( y-b \right)}^{2}}={{r}^{2}}$ , where (a,b) is the centre of the circle and r is the radius of the circle.
Therefore, we get, the center of the circle is (a, b) = (0,0) and ${{r}^{2}}=4$ ,
Taking the square root, we get,
$r=2$ .
Now, let’s consider the line we have been given.
The equation of the line that is given is $12x-5y+9=0$ .
Writing the equation in the form $y=mx+c$ we get,
\begin{align} & 12x-5y+9=0 \\ & 5y=12x+9 \\ & y=\dfrac{12}{5}x+\dfrac{9}{5}..........(i) \\ \end{align}
Comparing with $y=mx+c$ we get, ${{m}_{1}}=\dfrac{12}{5}$ and $c=\dfrac{9}{5}$ .
We need to find the tangent that is perpendicular to this line.
We need to know that the product of slopes of two perpendicular lines is -1.
Therefore, we know the value of ${{m}_{1}}=\dfrac{12}{5}$ we need to find the slope of ${{m}_{2}}$ .
${{m}_{1}}.{{m}_{2}}=-1...............(ii)$
Therefore, by substituting we get,
$\dfrac{12}{5}\times {{m}_{2}}=-1$
Solving we get,
\begin{align} & {{m}_{2}}=-1\times \dfrac{5}{12} \\ & =\dfrac{-5}{12} \end{align}
Therefore, the slope of the tangent is $\dfrac{-5}{12}$ .
Hence, by $y=mx+c$ substituting the value of ${{m}_{2}}$ we get,
$y=\dfrac{-5}{12}x+c.......................(iii)$
Now, we need to find the value of c.
This is the equation of the tangent therefore, it intersects the circle at that point and the centre is at the distance of radius.
We can use the formula for perpendicular distance (d) of a line $Ax+By+C=0$ from a point $O\left( {{x}_{1}},{{y}_{1}} \right)$ is given by,
$d=\dfrac{\left| A{{x}_{1}}+B{{y}_{1}}+C \right|}{\sqrt{{{A}^{2}}+{{B}^{2}}}}..........(iv)$
Here, d = radius = 2units, A = $\dfrac{-5}{12}$ , B = -1, C = c, $\left( {{x}_{1}},{{y}_{1}} \right)=\left( 0,0 \right)$ .
Substituting we get,
$2=\dfrac{\left| \left( \dfrac{-5}{12}\times 0 \right)+\left( -1\times 0 \right)+c \right|}{\sqrt{{{\left( \dfrac{-5}{12} \right)}^{2}}+{{\left( -1 \right)}^{2}}}}$
Solving the equation, we get,
\begin{align} & \left| c \right|=2\times \sqrt{{{\left( \dfrac{-5}{12} \right)}^{2}}+{{\left( -1 \right)}^{2}}} \\ & \left| c \right|=2\times \sqrt{\dfrac{25}{144}+1} \\ & =2\times \sqrt{\dfrac{169}{144}} \\ & =2\times \dfrac{13}{12} \\ & =\dfrac{13}{6} \end{align}
Therefore, the value is $\left| c \right|=\dfrac{13}{6}$ ,
Taking the modulus out we get,
$c=\dfrac{13}{6},\dfrac{-13}{6}$ .
Substituting the values in equation (iii) we get,
$y=\dfrac{-5}{12}x+\dfrac{13}{6}$ and $y=\dfrac{-5}{12}x-\dfrac{13}{6}$
Simplifying we get,
$5x+12y=26$ and $5x+12y=-26$ .
Plotting the diagrams all the figure, we get,

Hence, the equation of the tangents to the circle ${{x}^{2}}+{{y}^{2}}=4$ which are perpendicular to the line $12x-5y+9=0$ .

Note: We need to consider both the solutions of the value of c as we open the modulus sign as there will be two pairs of tangents satisfying the same condition. Also, the radius is always perpendicular to the tangent of the circle hence, we can use the formula for the distance of the between the centre and the tangent to the circle. As we can see in the diagram that the point of intersection of the two lines and the point of tangent are not the same. Also, the two values of see give the two lines one above the circle and one below the circle.


text:
# Distributed Learning with Compressed Gradient Differences

Training very large machine learning models requires a distributed computing approach, with communication of the model updates often being the bottleneck. For this reason, several methods based on the compression (e.g., sparsification and/or quantization) of the updates were recently proposed, including QSGD (Alistarh et al., 2017), TernGrad (Wen et al., 2017), SignSGD (Bernstein et al., 2018), and DQGD (Khirirat et al., 2018). However, none of these methods are able to learn the gradients, which means that they necessarily suffer from several issues, such as the inability to converge to the true optimum in the batch mode, inability to work with a nonsmooth regularizer, and slow convergence rates. In this work we propose a new distributed learning method---DIANA---which resolves these issues via compression of gradient differences. We perform a theoretical analysis in the strongly convex and nonconvex settings and show that our rates are vastly superior to existing rates. Our analysis of block-quantization and differences between ℓ_2 and ℓ_∞ quantization closes the gaps in theory and practice. Finally, by applying our analysis technique to TernGrad, we establish the first convergence rate for this method.

## Authors

• 19 publications
• 19 publications
• 44 publications
• 124 publications
06/09/2021

### EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback

Error feedback (EF), also known as error compensation, is an immensely p...
12/27/2019

### Evolution Strategies Converges to Finite Differences

Since the debut of Evolution Strategies (ES) as a tool for Reinforcement...
10/07/2021

### EF21 with Bells Whistles: Practical Algorithmic Extensions of Modern Error Feedback

First proposed by Seide (2014) as a heuristic, error feedback (EF) is a ...
06/17/2021

### On Effects of Compression with Hyperdimensional Computing in Distributed Randomized Neural Networks

A change of the prevalent supervised learning techniques is foreseeable ...
12/14/2020

### Quantizing data for distributed learning

We consider machine learning applications that train a model by leveragi...
06/07/2021

### Smoothness-Aware Quantization Techniques

Distributed machine learning has become an indispensable tool for traini...
01/18/2021

### Inference for BART with Multinomial Outcomes

The multinomial probit Bayesian additive regression trees (MPBART) frame...
##### This week in AI

Get the week's most popular data science and artificial intelligence research sent straight to your inbox every Saturday.

## 1 Introduction

Big machine learning models are typically trained in a distributed fashion. In this paradigm, the training data is distributed across several workers (e.g., nodes of a cluster), all of which compute in parallel an update to the model based on their local data. For instance, they can all perform a single step of Gradient Descent (GD

SGD). These updates are then sent to a parameter server which performs aggregation (typically this means just averaging of the updates) and then broadcasts the aggregated updates back to the workers. The process is repeated until a good solution is found.

When doubling the amount of computational power, one usually expects to see the learning process finish in half time. If this is the case, the considered system is called to scale linearly. For various reasons, however, this does not happen, even to the extent that the system might become slower with more resources. At the same time, the surge of big data applications increased the demand for distributed optimization methods, often requiring new properties such as ability to find a sparse solution. It is, therefore, of great importance to design new methods that are versatile, efficient and scale linearly with the amount of available resources.

In fact, the applications vary a lot in their desiderata. There is a rising interest in federated learning [Konečný et al., 2016], where the main concerns include the communication cost and ability to use local data only in an attempt to provide a certain level of privacy. In high-dimensional machine learning problems, nonsmooth

-penalty is often utilized, so one wants to have a support for proximable regularization. The efficiency of deep learning, in contrast, is dependent on heavy-ball momentum and nonconvex convergence to criticality, while sampling from the full dataset might not be an issue. In our work, we try to address all of these questions correspondingly.

### 1.1 Communication as the bottleneck

The the main aspects of distributed optimization efficiency are computational and communication complexity. In general, evaluating full gradients is intractable due to time and memory restrictions, so computation is made cheap by employing stochastic updates. On the other hand, in typical distributed computing architectures, communication is much slower (see Figure 1 for our experiments with communication cost of aggregating and broadcasting) than a stochastic update, and the design of a training algorithm needs to find a trade-off between them. There have been considered several ways of dealing with this issue.

One of the early approaches is to have each worker perform a block coordinate descent step  [Richtárik and Takáč, 2016, Fercoq et al., 2014]. By choosing the size of the block, one directly chooses the amount of data that needs to be communicated. An alternative idea is for each worker to do more work between communication rounds (e.g., by employing a more powerful local solver, such as a second order method), so that computation roughly balances out with communication. The key methods in this sphere include CoCoA and its variants [Jaggi et al., 2014, Ma et al., 2015, 2017b, 2017a, Smith et al., 2018], DANE [Shamir et al., 2014], DiSCO [Zhang and Xiao, 2015, Ma and Takáč, 2015], DANCE [Jahani et al., 2018] and AIDE [Reddi et al., 2016].

### 1.2 Update compression via randomized sparsification and/or quantization

Practitioners also suggested a number of heuristics to find a remedy for the communication botlleneck. Of special interest to this paper is the idea of compressing SGD updates, proposed by

Seide et al. [2014]. Building off of this work, Alistarh et al. [2017] designed a variant of SGD that guarantees convergence with compressed updates. Other works with SGD update structure include [Konečný and Richtárik, 2016, Bernstein et al., 2018, Khirirat et al., 2018]. Despite proving a convergence rate, [Alistarh et al., 2017]

also left many new questions open and introduced an additional, unexplained, heuristic of quantizing only vector blocks. Moreover, their analysis implicitly makes an assumption that all data should be available to each worker, which is hard and sometimes even impossible to satisfy.

In a concurrent with [Alistarh et al., 2017] work [Wen et al., 2017], the Terngrad method was analyzed for stochastic updates that in expectation have positive correlation with the vector pointing to the solution. While giving more intuition about convergence of quantized methods, this work used norm for quantization, unlike -quantization of [Alistarh et al., 2017]. This introduces another question of which norm is better suited for applications, which we also aim to answer in this work.

### 1.3 The problem

In this paper we focus on the problem of training a machine learning model via regularized empirical risk minimization:

 minx∈Rdf(x)+R(x)def=1nn∑i=1fi(x)+R(x). (1)

Above, is a closed convex regularizer, and is the loss of model obtained on data points belonging to distribution :

 fi(x)def=Eζ∼Diϕ(x,ζ).

Note that we do not assume any kind of similarity between distributions . In contrast, we allow them to be arbitrary meaning that functions may have completely different minimizers. Furthermore, we will assume that every has its own smoothness parameter

, so it is permitted to use utterly non-uniform distributions. As a special case where

, we recover the framework of one distribution, consideration of which leads to a purely stochastic method.

### 1.4 Notation

By we denote the sign of (-1 if , 0 if and if ). The th element of a vector is denoted as . For and , the norm of is . Note that for all . By we denote the number of nonzero elements of . For the detailed description of the notation see the Table 5 in the appendix.

## 2 Contributions

DIANA. We develop a distributed gradient-type method with compression of gradient differences, which we call DIANA (Algorithm 1).

Rate in the strongly convex case. We show that when applied to the smooth strongly convex minimization problem with arbitrary closed convex regularizer, DIANA has the iteration complexity , to a ball with center at the optimum (see Section 4.2, Theorem 2 and Corollary 1 for the details). In the case of decreasing stepsize we show iteration complexity (see Section 4.6, Theorem 5 and Corollary 2 for the details). Unlike in [Khirirat et al., 2018], in a noiseless regime our method converges to the exact optimum, and at a linear rate.

Rate in the non-convex case. We prove that DIANA also works for smooth non-convex problems with an indicator-like regularizer and get the iteration complexity (see Section 5, Theorem 4 and Corollary 3 for the details).

DIANA with momentum. We study momentum version of DIANA for the case of smooth non-convex objective with constant regularizer and (see Section J, Theorem 7 and Corollary 7 for the details).

First rate for Terngrad. We provide first convergence rate of TernGrad and provide new tight analysis of 1-bit QSGD under less restrictive assumptions for both smooth strongly convex objectives with arbitrary closed convex regularizer and non-convex objective with indicator-like regularizer (see Section 3.6 for the detailed comparison). Both of these methods are just special cases of our Algorithm 2 which is also a special case of Algorithm 1 with and for all . We show that Algorithm 2 has iteration complexity of convergence to the ball with center at the optimum in the case of the smooth strongly convex minimization problem with arbitrary closed convex regularizer (see Theorem 10) and in the case of non-convex minimization problem with indicator-like regularizer (see Theorem 8 and Corollary 8).

QSGD and Terngrad with momentum. We study momentum version of DIANA for and, in particular, we propose momentum versions of (1-bit) QSGD and TernGrad the case of smooth non-convex objective with constant regularizer and (see Section K.3, Theorem 9 and Corollary 9 for the details).

Optimal norm power. We find the answer for the following question: which norm to use for quantization in order to get the best iteration complexity of the algorithm? It is easy to see that all the bounds that we propose depend on where is an increasing function of (see Lemma 2 for the details). That is, for both Algorithm 1 and 2 the iteration complexity reduces when is growing and the best iteration complexity for our algorithms is achieved for . It implies that TernGrad has better iteration complexity than 1-bit QSGD.

First analysis for block-quantization. We give a first analysis of block-quantization (i.e. bucket-quantization). It was only mentioned in the paper Alistarh et al. [2017] that it is possible to get better convergence via block-quantization, but the authors do not have rigorous analysis of block-quantization. So, we close this gap.

We summarize a few key features of our complexity results established in Table 1.

## 3 The Algorithm

In this section we describe our main method—DIANA. However, we first need to introduce several key concepts and ingredients that come together to make the algorithm.

In each iteration of DIANA

, each node will sample an unbiased estimator of the local gradient. We assume that these gradients have bounded variance.

For every , . Moreover, the variance is bounded:

 E∥gki−∇fi(xk)∥22≤σ2i. (2)

Note that is an unbiased estimator of :

 E[gk|xk]=1nn∑i=1∇fi(xk)=∇f(xk). (3)

Moreover, by independence of the random vectors , its variance is bounded above by

 E[∥gk−∇f(xk)∥22|xk]≤σ2n, (4)

where .

### 3.2 Quantization

DIANA applies random compression (quantization) to gradient differences, which are then communicated to a parameter server. We now define the random quantization transformations used. Our first quantization operator transforms a vector into a random vector whose entries belong to the set for some .

###### Definition 1 (p-quantization).

Let and let . If , we define . If , we define by setting

 ˜Δ(j)=∥Δ∥psign(Δ(j))ξ(j),j=1,2,…,d, (5)

where

are Bernoulli random variables

111That is,

with probability

(observe that this quantity is always upper bounded by 1) and with probability .
. Note that

 ˜Δ=∥Δ∥psign(Δ)∘ξ, (6)

where is applied elementwise, and denotes the Hadamard (i.e. elementwise) product. We say that is -quantization of . When sampling , we shall write .

In addition, we consider a block variant of -quantization operators.

###### Definition 2 (block-p-quantization).

Let , where , and for all . We say that is -quantization of with sizes of blocks and write if for all .

In other words, we quantize subvectors called blocks of the initial vector. Note that in the special case when we get full quantization: . Note that we do not assume independence of the quantization of blocks or independence of .

The next result states that is an unbiased estimator of , and gives a formula for its variance.

###### Lemma 1.

Let and . Then for

 E^Δ(l)=Δ(l),E∥^Δ(l)−Δ(l)∥22=Ψl(Δ), (7)
 E^Δ=Δ,E∥^Δ−Δ∥22=Ψ(Δ), (8)

where

 x=(x(1)⊤,x(2)⊤,…,x(m)⊤)⊤,
 Ψl(x)def=∥x(l)∥1∥x(l)∥p−∥x(l)∥22≥0, (9)
 Ψ(x)def=m∑l=1Ψl(x)≥0. (10)

Thus, is an unbiased estimator of . Moreover, the variance of is a decreasing function of , and is minimized for .

### 3.3 Communication cost

If bits are used to encode a float number, then at most bits are needed to communicate with Elias coding (see Theorem 3.3 in [Alistarh et al., 2017]). In our next result, we given an upper bound on the expected communication cost.

###### Theorem 1 (Expected sparsity).

Let and be its -quantization. Then

 E∥˜Δ∥0=∥Δ∥1∥Δ∥p≤∥Δ∥1−1/p0≤~d1−1/p, (11)

and

 Cpdef=EC(˜Δ)≤∥Δ∥1/21∥Δ∥1/2p(log~d+log2+1)+b. (12)

All expressions in (11) and (12) are increasing functions of .

### 3.4 Proximal step

Given , the proximal operator for the regularizer is defined as

 proxγR(u)def=argminv{γR(v)+12∥v−u∥22}.

The proximal operator of a closed convex function is nonexpansive. That is, for any and ,

 ∥∥proxγR(u)−proxγR(v)∥∥2≤∥u−v∥2. (13)

### 3.5 Diana

In DIANA, each machine first computes a stochastic gradient at current iterate . We do not quantize this information and send it off to the parameter server as that approach would not converge for . Instead, we maintain memory at each node (initialized to arbitrary values), and quantize the difference instead. Both the node and the parameter server update in an appropriate manner, and a proximal gradient descent step is taken with respect to direction , where is a momentum parameter, whereas is an unbiased estimator of the full gradient, assembled from the memory and the transmitted quantized vectors. Note that we allows for block quantization for more flexibility. In practice, we want the transmitted quantized vectors to be much easier to communicate than the full dimensional vector in , which can be tuned by the choice of defining the quantization norm, and the choice of blocks.

### 3.6 Relation to Qsgd and TernGrad

If the initialization is done with and , our method reduces to either 1-bit QSGD or TernGrad with and respectively. We unify them in the Algorithm 2. We analyse this algorithm (i.e. DIANA with and ) in three cases: 1) smooth strongly convex objective with arbitrary closed convex regularizer; 2) smooth non-convex objective with constant regularizer; 3) smooth non-convex objective with constant regularizer for the momentum version of the algorithm. We notice, that in the original paper Wen et al. [2017] authors do not provide the rate of convergence for TernGrad and we get the convergence rate for the three aforementioned situations as a special case of our results. Moreover, we emphasize that our analysis is new even for 1-bit QSGD, since in the original paper Alistarh et al. [2017] authors consider only the case of bounded gradients (), which is very restrictive assumption, and they do not provide rigorous analysis of block-quantization as we do. In contrast, we consider more general case of block-quantization and assume only that the variance of the stochastic gradients is bounded, which is less restrictive assumption since the inequality implies .

We obtain the convergence rate for arbitrary for the three aforementioned cases (see Theorems 891011 and Corollaries 8910 for the details) and all obtained bounds becomes better when is growing, which means that TernGrad has better iteration complexity than QSGD and, more generally, the best iteration complexity attains for norm quantization.

## 4 Theory: Strongly Convex Case

### 4.1 Assumptions

Let us introduce two key assumptions of this section.

###### Assumption 2 (L–smoothness).

We say that a function is -smooth if

 f(x)≤f(y)+⟨∇f(y),x−y⟩+L2∥x−y∥22 (14)

for any and .

###### Assumption 3 (μ-strong convexity).

A function is called -strongly convex if for all and

 f(x)≥f(y)+⟨∇f(y),x−y⟩+μ2∥x−y∥22. (15)

### 4.2 Iteration complexity

For , define

 (16)
###### Lemma 2.

is increasing as a function of and decreasing as a function of . In particular, , and moreover,

 α1(d)=1d,α2(d)=1√d,α∞(d)=21+√d

and, as a consequence, for all positive integers and the following relations holds

 α1(˜d)=α1(d)d˜d,α2(˜d)=α2(d)√d˜d,
 α∞(˜d)=α∞(d)1+√d1+√˜d.
###### Theorem 2.

Assume the functions are –smooth and –strongly convex. Choose stepsizes and , block sizes , where , and parameter satisfying the following relations:

 1+ncα21+ncα≤αp% def=αp(˜d), (17)
 γ≤min{αμ,2(μ+L)(1+cα)}. (18)

Define the Lyapunov function

 Vkdef=∥xk−x∗∥22+cγ2nn∑i=1∥hki−h∗i∥22, (19)

where is the solution of (1) and . Then for all ,

 EVk≤(1−γμ)kV0+γμ(1+ncα)σ2n. (20)

This implies that as long as , we have

In particular, if we set to be equal to the minimum in (18), then the leading term in the iteration complexity bound is

 1γμ=max{1α,(μ+L)(1+cα)2μ}. (21)
###### Corollary 1.

Let , , , and . Then the conditions (17) and (18) are satisfied, and the leading term in the iteration complexity bound is equal to

 1γμ=max{2αp,(κ+1)(12−1n+1nαp)}. (22)

This is a decreasing function of . Hence, from iteration complexity perspective, is the optimal choice.

In Table 2 we calculate the leading term (43) in the complexity of DIANA for , each for two condition number regimes: (standard) and (large).

### 4.3 Matching the rate of gradient descent for quadratic size models

Note that as long as the model size is not too big; in particular, when the linear rate of DIANA with is , which matches the rate of gradient descent.

### 4.4 Optimal number of nodes

In practice one has access to a finite data set, consisting of data points, where is very large, and wishes to solve an empirical risk minimization (“finite-sum”) of the form

 minx∈Rdf(x)=1NN∑i=1ϕi(x)+R(x), (23)

where each is –smooth and -strongly convex. If compute nodes of a distributed system are available, one may partition the functions into groups, , each of size , and define Note that Note that each is also –smooth and –strongly convex.

This way, we have fit the original (and large) problem (23) into our framework. One may now ask the question: How many many nodes should we use (other things equal)? If what we care about is iteration complexity, then insights can be gained by investigating Eq. (43). For instance, if , then the complexity is

 W(n)def=max{2√d√m,(κ+1)(12−1n+√dn√m)}.

The optimal choice is to choose so that the term becomes (roughly) equal to : This gives the formula for the optimal number of nodes

 n∗=n(d)def=2(√dm−1),

and the resulting iteration complexity is . Note that is increasing in . Hence, it makes sense to use more nodes for larger models (big ).

### 4.5 Optimal block quantization

If the dimension of the problem is large, it becomes reasonable to quantize vector’s blocks, also called blocks. For example, if we had a vector which consists of 2 smaller subvectors each of which is proportional to the vector of all ones, we can transmit just the subvectors without any loss of information. In the real world, we have a similar situation when different parts of the parameter vector have different scale. A straightforward example is deep neural networks, layers of which have pairwise different scales. If we quantized the whole vector at once, we would zero most of the update for the layer with the smallest scale.

Moreover, our theory says that if we have workers, then the iteration complexity increase of quantization is about . However, if quantization is applied to a block of size , then this number becomes 1, implying that the complexity remains the same. Therefore, if one uses about 100 workers and splits the parameter vector into parts of size about 10,000, the algorithm will work as fast as SGD, while communicating bits instead of floats!

### 4.6 Decreasing stepsizes

We now provide a convergence result for DIANA with decreasing step sizes, obtaining a rate.

###### Theorem 3.

Assume that is -smooth, -strongly convex and we have access to its gradients with bounded noise. Set with some for some numbers and satisfying . After iterations of DIANA we have

 EVk≤1ηk+1max{V0,4(1+ncα)σ2nθμ},

where , and

is the standard deviation of the gradient noise.

###### Corollary 2.

If we choose , , , then there are three regimes:

1. if , then and to achieve we need at most iterations;

2. if , then and to achieve we need at most iterations;

3. if , then and to achieve we need at most iterations.

## 5 Theory: Nonconvex Case

In this section we consider the non-convex case.

###### Theorem 4.

Assume is such that exists a closed convex set satisfying 1) and 2) (e.g. indicator function of ). Also assume that , is -smooth, stepsizes and and parameter satisfying and is chosen randomly from . If, further, every worker samples from the full dataset, then

 E∥∇f(¯¯¯xk)∥22 ≤2kf(x0)−f∗+cγ2∥h0∥22γ(2−Lγ−cαLγ) +(1+cnα)Lγ2−Lγ−cαLγσ2n.
###### Corollary 3.

Set , , , and run the algorithm for iterations. Then, the final accuracy is at most .

Moreover, if the first term in Corollary 3 is leading and , the resulting complexity is , i.e. the same as that of SGD. For instance, if sufficiently large mini-batches are used, the former condition holds, while for the latter it is enough to quantize vectors in blocks of size .

## 6 Convergence Rate of TernGrad

Here we give the convergence guarantees for TernGrad and provide upper bounds for this method. The method coincides with Algorithm 2 for the case when . In the original paper [Wen et al., 2017] no convergence rate was given and we close this gap.

To maintain consistent notation we rewrite the TernGrad in notation which is close to the notation we used for DIANA. Using our notation it is easy to see that TernGrad is DIANA with and . Firstly, it means that for all and . What is more, this observation tells us that Lemma 3 holds for the iterates of TernGrad too. What is more, in the original paper [Wen et al., 2017] the quantization parameter was chosen as . We generalize the method and we don’t restrict our analysis only on the case of sampling.

As it was in the analysis of DIANA our proofs for TernGrad work under Assumption 1.

## 7 Implementation and Experiments

Following advice from Alistarh et al. [2017], we encourage the use of blocks when quantizing large vectors. To this effect, a vector can decomposed into a number of blocks, each of which should then be quantized separately. If coordinates have different scales, as is the case in deep learning, it will prevent undersampling of those with typically smaller values. Moreover, our theoretical results predict that applying quantization to blocks or layers will result in superlinear acceleration.

In our convex experiments, the optimal values of were usually around , where the minimum is taken with respect to blocks and are their sizes.

Finally, higher mini-batch sizes make the sampled gradients less noisy, which in turn is favorable to more uniform differences and faster convergence.

### 7.1 Diana with momentum works best

We implement DIANA, QSGD, TernGrad and DQGD in Python222The code will be made available online upon acceptance of this work. using MPI4PY for processes communication. This is then tested on a machine with 24 cores, each is Intel(R) Xeon(R) Gold 6146 CPU @ 3.20GHz. The problem considered is binary classification with logistic loss and penalty, chosen to be of order , where is the total number of data points. We experiment with choices of , choice of norm type , different number of workers and search for optimal block sizes. is always set to be zero vector for all . We observe that for -norm the optimal block size is significantly bigger than for -norm. Detailed description of the experiments can be found in Section L. Here, however, we provide Figure 2 to show how vast the difference is with other methods.

### 7.2 Diana vs MPI

In Figure 3 we compare the performance of DIANA vs. doing a MPI reduce operation with 32bit floats. The computing cluster had Cray Aries High Speed Network. However, for DIANA we used 2bit per dimension and have experienced a strange scaling behaviour, which was documented also in Chunduri et al. [2017]. In our case, this affected speed for alexnet and vgg_a beyond 64 or 32 MPI processes respectively. For more detailed experiments, see Section L.

### 7.3 Train and test accuracy on Mnist and Cifar10

In the next experiments, we run QSGD Alistarh et al. [2017], TernGrad Wen et al. [2017], SGD with momentum and DIANA

on Mnist dataset and Cifar10 dataset for 3 epochs. We have selected 8 workers and run each method for learning rate from

. For QSGD, DIANA and TernGrad, we also tried various quantization bucket sizes in . For QSGD we have chosen quantization levels. For DIANA we have chosen and have selected initial . For DIANA and SGD we also run a momentum version, with a momentum parameter in . For DIANA we also run with two choices of norm and . For each experiment we have selected softmax cross entropy loss. Mnist-Convex is a simple DNN with no hidden layer, Mnist-DNN is a convolutional NN described here https://github.com/floydhub/mnist/blob/master/ConvNet.py and Cifar10-DNN is a convolutional DNN described here https://github.com/kuangliu/pytorch-cifar/blob/master/models/lenet.py.

In Figure 4 we show the best runs over all the parameters for all the methods. For Mnist-Convex SGD and DIANA makes use of the momentum and dominate all other algorithms. For Mnist-DNN situation is very similar. For Cifar10-DNN both DIANA and SGD significantly outperform other methods.

## Acknowledgements

The work of Peter Richtárik was supported by the KAUST baseline funding scheme. The work of Martin Takáč was partially supported by the U.S. National Science Foundation, under award numbers NSF:CCF:1618717, NSF:CMMI:1663256 and NSF:CCF:1740796.

## Appendix A Basic Identities and Inequalities

Smoothness and strong convexity. If is -smooth and -strongly convex, then for any vectors we have

 ⟨∇f(x)−∇f(y),x−y⟩≥μLμ+L∥x−y∥22+1μ+L∥∇f(x)−∇f(y)∥22. (24)

Norm of a convex combination. For any and , we have

 ∥αx+(1−α)y∥22=α∥x∥22+(1−α)∥y∥22−α(1−α)∥x−y∥22. (25)

Variance decomposition. The (total) variance of a random vector is defined as the trace of its covariance matrix:

 V[g]def=Tr[E[(g−Eg)(g−Eg)⊤]]=E[Tr[(g−Eg)(g−Eg)⊤]]=E∥g−Eg∥22=d∑