CS- 6515-A: Intro to Grad Algorithms - CS-6515-A

Hey everyone,

Problem set 7 grades were released earlier today. You should be able to see your grade and any comments left by the graders on Gradescope. These are the statistics:

Rubric and Regrade Requests

Your graders are human, and so they may have made errors. If you think your assignment was graded incorrectly against the rubric, then make a regrade request to the instructors on Gradescope. Regrades will be open for SIX days until April 3rd at 11:59 PM (04-3-2025 @ 11:59 PM ET). Please submit a regrade before the deadline. Also, provide a brief explanation of the issue(s) and why you should receive points.

Some notes about regrade requests:

• Please read the rubric closely and use the solutions for reference before submitting a regrade request. 
• Note that we formally reserve the right to regrade your entire submission if you submit a regrade request. It is possible, though very unlikely, to end up losing points from submitting a regrade request.
• Regrade requests without an explanation of the issue/why points should be returned will be dismissed. 
• Note that regrades requests are for when you think the grading did not match the rubric, or if you think that the answer in the rubric is incorrect. Please do not submit a regrade request if you were graded correctly but feel that the rubric is unfair.

Handwritten notes:

https://piazza.com/class_profile/get_resource/m3icaapxwwz1f5/m8rughy1sv414o

Recording:

https://mediaspace.gatech.edu/media/CS6515%20L20%20Gradient%20Descent%20II/1_f6qw5mb3

Bubeck's optimization book http://sbubeck.com/Bubeck15.pdf

• Section 3.2 is on smooth functions
• Section 3.4.2 is on smooth & strongly convex functions

We did not complete the proof of convergence for Lipschitz functions.

Here are the handwritten notes that I had prepared for class, if you are interested in the proof.

https://piazza.com/class_profile/get_resource/m3icaapxwwz1f5/m8rughk8b4s143

Handwritten notes: https://piazza.com/class_profile/get_resource/m3icaapxwwz1f5/m8p04vvxw9h7nv

Recording: https://mediaspace.gatech.edu/media/CS%206515%20L19%20Gradient%20Descent%20I/1_e490et6i

Other material:

• Bubeck's convex optimization book, in particular section 3.2 http://sbubeck.com/Bubeck15.pdf (Theorem 3.3 and Lemma 3.4 are the same as in class, but the proof for 3.3 is a bit different.)

I would like to share this message from GT's Competitive Programming club:

GT Competitive Programming club is hosting our first GTCP Competition, which will be held on the Friday after spring break on March 28 at 3-6pm. It will be held at CoC 101.   It will be in teams of two and we will be giving prizes and medals to the top teams, as well as featuring your resumes to our sponsors, which include Google, IMC Trading, Millenium, AMD, and VISA. Grab your friends and sign up for the competition! There will be dinner served after the contest as well.   Sign up now at https://tinyurl.com/gtcp2025

GTCP_2025_Poster_1.pdf

If there are any questions about the competition and/or club, please contact professor Abrahim Ladha abrahimladha@gatech.edu who is the club advisor.

Since many of the techniques are relevant to this course (DP, D&C, etc) and we've also had similar programming homework questions, I've decided to count participation in the contest as one optional homework problem. (i.e., equivalent to scoring 20/20 points on one HW problem)

Remark: We continue to use the top 21 homework problems for the final grade. Skipping the contest will not negatively affect your grade.

Hey everyone,

Problem set 6 grades were released earlier today. You should be able to see your grade and any comments left by the graders on Gradescope. These are the statistics:

Rubric and Regrade Requests

Your graders are human, and so they may have made errors. If you think your assignment was graded incorrectly against the rubric, then make a regrade request to the instructors on Gradescope. Regrades will be open for FIVE days (after Spring Break) until March 28th at 11:59 PM (03-28-2025 @ 11:59 PM ET). Please submit a regrade before the deadline. Also, provide a brief explanation of the issue(s) and why you should receive points.

Some notes about regrade requests:

• Please read the rubric closely and use the solutions for reference before submitting a regrade request. 
• Note that we formally reserve the right to regrade your entire submission if you submit a regrade request. It is possible, though very unlikely, to end up losing points from submitting a regrade request.
• Regrade requests without an explanation of the issue/why points should be returned will be dismissed. 
• Note that regrades requests are for when you think the grading did not match the rubric, or if you think that the answer in the rubric is incorrect. Please do not submit a regrade request if you were graded correctly but feel that the rubric is unfair.

Handwritten notes: https://piazza.com/class_profile/get_resource/m3icaapxwwz1f5/m881ieu05uq1oq

Typed notes (same as L17): https://piazza.com/class_profile/get_resource/m3icaapxwwz1f5/m851e9sqsq91vp

Recording:

https://mediaspace.gatech.edu/media/CS6515%20L18%20Simplex%20Algorithm%20II/1_qyggfz40

Other material (same as L17)

• Books typically focus on proving correctness in which case it's mostly algebra. If you care about the details and why the algorithm is provably correct, they're a great resource. I like the following book, but again, it focuses more on proofs than building intuition about the simplex algorithm. https://www.dropbox.com/scl/fi/4b3trc6ftjyrm7i37b79o/Simplex-PapadimitriouSteiglitzCombOpt.pdf?rlkey=4aw2pke3rgszplhzpvi2zvr78&st=eu4dpgvd&dl=0
• DPV section 7.4
• If you look for information online (eg videos on the simplex algorithm on youtube), many resources will teach you how to run the simplex algorithm by hand. That is not the focus of our class. (I just wanted to make that clear before you spend time practicing to run simplex by hand.) Also be not be surprised if their algorithm looks slightly different. There are different variants (primal simplex, dual simplex, revised simplex etc). Some pick B as a set of rows. Others pick B as a set of columns. Some are explained algebraically (and look similar to Gaussian elimination) rather than using geometry.

Hi everyone,

You can join my office hours today using this link: https://gatech.zoom.us/j/7091838494