Papers and Reading material

Lectures 1,2,3

General

  1. Boyd & Vandenberghe, Convex Optimization

  2. Boyd, EE364A, Stanford

  3. Boyd, EE364B, Stanford

  4. EE236C, Vandenberghe, UCLA

  5. EE227A, Sra, UC Berkeley

Lectures 4 and 5

General Background

  1. Motwani, Raghavan (Randomized Algorithms), 1995

Lecture 4

  1. Goemans, Williamson, 1995

  2. Khot, Naor, 2011 (Grothendieck type inequalities - very theoretical)

  3. Briet, Filho, Vallentin, 2010 (Grothendieck problem with rank constraint)

Lecture 5

  1. Charikar, 1995 (Similarity estimation and rounding)

  2. Broder, 2005 (Shingling lecture notes)

  3. Broder, 2000 (Identifying and Filtering Near-Duplicate Documents)

  4. Ahmed, Ravi, Narayanamurthy, Smola, 2012 (FastEx clustering)

Lecture 19

  1. Bertsekas, 2011, Survey on incremental gradient, subgradient, proximal methods

General

  1. D. P. Bertsekas, “Stochastic optimization problems with nondifferentiable cost functionals,” J. Optim. Theory Appl. (JOTA), vol. 12, no. 2, pp. 218-231, 1973. (Very nicely written paper; includes a clean proof of subdifferentials of convex functions given by expectations).
    [BibTeX] [Local PDF]

    @article{bertsekas1973,
      author = {D. P. Bertsekas},
      title = {Stochastic optimization problems with nondifferentiable cost functionals},
      journal = {J. Optim. Theory Appl. (JOTA)},
      year = {1973},
      volume = {12},
      number = {2},
      pages = {218--231},
      note = {(Very nicely written paper; includes a clean proof of subdifferentials of convex functions given by expectations)},,
      file ={./papers/1973_bertsekas_stochastic_optimization_problems_nondifferentiable_cost_functionals.pdf}
    }
    
  2. W. Fenchel, “On conjugate convex functions,” Canadian Journal of Mathematics, vol. 1, no. 1, pp. 73-77, 1949. (Fenchel's influential paper on conjugates to convex functions; must read).
    [BibTeX] [Local PDF]

    @article{fenchel1949,
      author = {Fenchel, W},
      title = {On conjugate convex functions},
      journal = {Canadian Journal of Mathematics},
      year = {1949},
      volume = {1},
      number = {1},
      pages = {73--77},
      note = {(Fenchel's influential paper on conjugates to convex functions; must read)},,
      file ={./papers/1949_fenchel_conjugate_convex_functions.pdf}
    }
    
  3. J. Jensen, “Sur les fonctions convexes et les inégalités entre les valeurs moyennes,” Acta Mathematica, vol. 30, no. 1, pp. 175-193, 1906. (Classic paper on convex functions; a must-read for all those who care about convexity).
    [BibTeX] [URL] [Local PDF]

    @article{jensen1906,
      author = {Jensen, J.L.W.V.},
      title = {Sur les fonctions convexes et les inégalités entre les valeurs moyennes},
      journal = {Acta Mathematica},
      publisher = {Kluwer Academic Publishers},
      year = {1906},
      volume = {30},
      number = {1},
      pages = {175-193},
      note = {(Classic paper on convex functions; a must-read for all those who care about convexity)},
      url = {http://dx.doi.org/10.1007/BF02418571},
      doi = {http://dx.doi.org/10.1007/BF02418571},,
      file ={./papers/1906_jensen_sur_les_fonctions_convexes_et_les_inegalites_entre_valeurs_moyennes.pdf}
    }
    
  4. J. J. Moreau, “Fonctions convexes duales et points proximaux dans un espace hilbertien,” C. R. Acad. Sci. Paris Sér. A Math., vol. 255, pp. 2897-2899, 1962. (Original paper which launched proximity operators).
    [BibTeX]

    @article{moreau1962,
      author = {Moreau, J J},
      title = {Fonctions convexes duales et points proximaux dans un espace hilbertien},
      journal = {C. R. Acad. Sci. Paris Sér. A Math.},
      year = {1962},
      volume = {255},
      pages = {2897--2899},
      note = {(Original paper which launched proximity operators)},
    }
    
  5. R. T. Rockafellar, “Monotone Operators and the Proximal Point Algorithm,” SIAM Journal on Control and Optimization, vol. 14, no. 5, pp. 877-898, August 1976. (This paper is one of the most important papers in the class of proximity-operator based algorithsm; the classic paper that lies at the heart of so many subsequent works.).
    [BibTeX] [Local PDF]

    @article{rockafellar1976,
      author = {Rockafellar, R. Tyrrell},
      title = {Monotone Operators and the Proximal Point Algorithm},
      journal = {SIAM Journal on Control and Optimization},
      year = {1976},
      volume = {14},
      number = {5},
      pages = {877--898},
      note = {(This paper is one of the most important papers in the class of proximity-operator based algorithsm; the classic paper that lies at the heart of so many subsequent works.)},
      doi = {http://dx.doi.org/10.1137/0314056},,
      file ={./papers/1976_rockafellar_monotone_operators_proximal_point_algorithm.pdf}
    }