text:
Date & Time TBD - All Screenings at Velour, Downtown Provo
SCHEDULE & BLOCK INFORMATION TBD (LIKELY SPRING 2021)
NEED ANYTHING (USA)
SYNOPSIS: A paranoid woman commits to poisoning her roommate who she believes is infected with a deadly virus – but it doesn't quite work the way she planned.
RATINGS GUIDE: Mild Violence
DIRECTOR: Buz Wallick
PREMIERE STATUS: Utah Premiere
AWARDS NOMINATIONS: TBD
DIRECTOR'S BIO: Buz Wallick was born and raised in the town of Paradise, California where he grew up on a healthy diet of Jaws, Arachnophobia, and other creature features. Buz has the unique background of being entirely self taught and has worked on over 100 projects over the past 10 years in Los Angeles. With his extensive knowledge of film production Buz does what he loves to do; tell stories through the art of cinema.
IMAGES FROM THE FILM:
NIGHT CRAWL (USA)
SYNOPSIS: Two inmates tunneling out of a hellish prison discover something more terrifying than death row.
RATINGS GUIDE: Violence, Intense Imagery
DIRECTOR: Gregory Shultz
GENRE: Horror, The Beyond, Fantastic
DIRECTOR'S BIO: An Ozarkian filmmaker of the spooky kind. Based in Los Angeles.
TRAILER: N/A
ODD GIRL (CANADA)
SYNOPSIS: Set in a small suburban town, high school student Dylan becomes worried when his popular down-to-earth best friend starts getting followed incessantly by the odd girl out. Her admiration seems harmless and innocent to his friend, but Dylan isn't so sure…
RATINGS GUIDE: Mild Language
DIRECTOR: Rami Kahlon
PREMIERE STATUS: Regional Premiere
DIRECTOR'S BIO: Rami Kahlon is a professional actor, published writer, and award-winning director from Surrey, BC. Her twisted eye has left her with a love for all things horror, and she is proud to be presenting her directorial debut "Odd Girl" with all of you at FilmQuest. Give her a follow on Instagram at @ramikahlon to keep up with her film shenanigans.
OVERKILL (USA)
SYNOPSIS: A comedic take on a familiar setup: when too-woke-for-their-own-good college kids are terrorized by an unstoppable masked killer, the final girl must outsmart him to survive. Only in this movie, the killer literally cannot be stopped (or killed).
RATINGS GUIDE: Violence, Mild Language, Adult Content, Intense Imagery
DIRECTOR: Alex Montilla
GENRE: Horror, Comedy
DIRECTOR'S BIO: I've been making movies since high school. When my friends and I took over the morning announcements, we saw an opportunity to make short films for a captive audience…and by that, I mean an audience that literally HAD to watch; the entire school was held hostage by our silliness. Out of necessity, I learned the basics of filmmaking: acting, writing, directing, editing, visual effects, scoring…you name it; I was the Robert Rodriguez of morning announcements. All of these skills came in handy when I attended the University of Miami's film school. After making the leap to Los Angeles, I've continued to hone my craft by working in the editing room for studio films like "Hot Tub Time Machine" and "The Muppets", on the sets of films like "The Hangover Part III" and as a Producer for ESPN. All the while, I continue to write, direct and edit my own films.
PAKOK (USA)
SYNOPSIS: With the dry season closing in on her desolate family farm, a young girl becomes possessed by the ghost of a chicken she was forced to slaughter.
DIRECTOR: Cody Holland
PREMIERE STATUS: World Premiere
DIRECTOR'S BIO: A graduate of the Florida State University College of Motion Picture Arts, Cody Holland moved to Los Angeles in 2014 to pursue a career as a horror director. Within a year of arriving in California, he was hired as head editor at Omaze, a fundraising company that specializes in viral video content. Since starting there, he has cut projects for the likes of Disney, Marvel and LucasFilm. Pakok is his first directorial project since 2013.
PETER THE PENGUIN (UK)
SYNOPSIS: Nigel is on his way to meet his partner's daughter, Emily, for the first time and he hopes to make a big impression.
RATINGS GUIDE: Mild Violence, Mild Language, Intense Imagery
DIRECTOR: Andrew Rutter
DIRECTOR'S BIO: Andrew is a Writer/Director based in the UK focusing on short films, commercials and music videos. His latest music video was UKMVA nominated and his short films have screened globally at BAFTA & Oscar qualifying festivals..
PIECES OF ME (USA)
SYNOPSIS: A struggling young starlet uncovers a deadly secret which may be the key to the fame and fortune she so desperately craves.
RATINGS GUIDE: Strong Violence, Mild Language, Intense Imagery
DIRECTOR: Julia Max
PREMIERE STATUS: USA Premiere
DIRECTOR'S BIO: Julia is an LA native who grew up on film sets, and graduated from USC. Her short films THE COLONIES and DISTORTION played at film festivals around the country. She is currently working on a feature length version of PIECES OF ME.
PIGS (FRANCE / USA)
SYNOPSIS: A young woman must use everything at her disposal to escape her captor after she is locked into a farmhouse attic. But what was she doing out in the fields in the first place?
RATINGS GUIDE: Strong Violence, Mild Language, Adult Content< Intense Imagery
DIRECTOR: Nicolas Alvo
DIRECTOR'S BIO: Born and raised in Santiago, Chile and a graduate of NYU Tisch, Nico is an award winning film and theater director, actor, producer and general swiss army knife. His company, Primordial Jam Productions, has produced over 30 short films, music videos and other projects since its foundation in 2015.
PLAINSONG (CANADA)
SYNOPSIS: Three friends on vacation by the sea are spellbound by a supernatural force.
RATINGS GUIDE: Brief Nudity
DIRECTOR: Alexis Fortier Gauthier
GENRE: The Beyond, Fantastic
DIRECTOR'S BIO: Alexis Fortier Gauthier is an original and prolific filmmaker trained at UQAM and INIS in Montreal. His shorts have been programmed in an array of international festivals and, in 2016, Fortier Gauthier's talent get more widely acknowledged with the collective feature-length film about sham and creativity Of Ink and Blood.
POLVOTRON 500 (SPAIN)
SYNOPSIS: Year 2065. Charly is a gray man in a world without hope dominated by large corporations, where everything has a price, even to rest without being besieged by publicity. Charly habitually sleep in an old holographic booth, POLVOTRÓN 500, where you arrange so that nobody bothers.
RATINGS GUIDE: Adult Content
DIRECTOR: Silvia Conesa
GENRE: Sci-Fi, Comedy
PREMIERE STATUS: North America Premiere
DIRECTOR'S BIO: Actress, Director and writer from Cartagena (Spain). She studied cinematographic script at the Madrid Film Institute and Master in Film Direction at the Superior School of Cinema and Audiovisuals of Catalonia (ESCAC). As an actress she has worked in theater, film and television since 2009. In 2017 she writes, directs and produces the short film Evströnger, obtaining several awards and more than 100 national and international selections, among which are "Mórbido Fest", "Fantafestival", "Athens International Film + Video Festival "and" Medina del Campo ". In 2018 he created his own fiction producer company"Gerión Films", especially oriented to the fantastic genre. It is under this label that she directs two science fiction films: "Shagomatic 500" and Hamelin, the last one in post-production
POSTMARKED (USA)
SYNOPSIS: Young Scooter, his God fearing father Lionel, and his brother Tyler used to be a big happy family who lived at the end of a cul de sac on a Mart, Texas Street. However, when Tyler comes out as transgender and reveals she wants to be identified as Ty, she's met with adversity from family and friends alike, forcing her to flee home from the tender young age of 17.
RATINGS GUIDE: Malakai
DIRECTOR: Alexandra Emmons & Andrew Juhl
DIRECTOR'S BIO: Malakai is an artist, director and philanthropist who has made it her mission to be a disruptor by telling world-building and fantastical narratives that turn archetypes of the black diaspora on it's head. Malakai received her start within the narrative world in 2016, as one of the Horizon Award Winners, where her film premiered at Sundance and where she was mentored by Cassian Elwes, Christine Vachone and Lynette Howell for her short film, Suffering. Her short film Souls STARRING Tabitha Brown (Executive produced by Anna Hashmi & produced by Stephen Love & Marquita Bradley), has gained critical acclaim in festivals such as American Black Film Festival, Reel Sisters & The Pan African Film Festival. Souls premiered in 2018 at the Phoenix Art Museum where Malakai was a recipient of the Contemporary Forum Artist grant. Malakai was also one of the 2019 ATT Hello Lab Directing fellows, where her recent short film, Postmarked was executive produced by Lena Waithe and Rishi Rajani, starring Loretta Devine, Rob Morgan and Jaylin Fletcher and written by Angela Carbone. The film was also distributed by Direct TV.
PUBLIC LOT (USA)
SYNOPSIS: A man witnesses something he shouldn't.
DIRECTOR: Chris Beier
GENRE: Fantastic, Thriller
DIRECTOR'S BIO: I've made a few short films and am gearing up for a feature. My day job is in the doc world. Please feel free to reach out!
PUSH THE POINT (USA)
SYNOPSIS: A musical short film set between the worlds of fandom and pop culture, PUSH THE POINT follows four online gamers through their squad-based mission. Harder than defeating the red team however, is sticking together while trying to navigate toxicity, super-fandom, and the futility of having an argument on the internet.
RATINGS GUIDE: Adult Content, Mild Language
DIRECTOR: Bryan Burton
DIRECTOR'S BIO: Bryan Burton is a NYC-based actor/director from North Carolina (UNC-Chapel Hill alum), with 15+ years of work in TV, film, theatre, VO, comedy improv, sketch comedy, comedy writing, and cat sitting. Some of his favorite TV & film credits include his recurring and regular roles on HBO's Emmy Award-winning limited series THE NIGHT OF opposite John Turturro, HBO's Emmy Award-winning series SUCCESSION opposite Kieran Culkin, Adult Swim's live action comedy series NEON JOE WEREWOLF HUNTER opposite Jon Glaser, Scott Adsit, Stephanie March, Reg E. Cathy, and TruTV's comedy series JON GLASER LOVES GEAR, as well as roles opposite George Clooney and Jack O'Connell in Jodie Foster's MONEY MONSTER, Ben Kingsley in Isabel Coixet's LEARNING TO DRIVE, Logan Lerman in James Schamus' INDIGNATION, and more. // Bryan-Burton.com // PushThePoint.com // Instagram: @bryanburton
RATTENFALLE (USA)
SYNOPSIS: A contemporary, silent, black & white film exploring the horrors of modern cuisine and the palatability of revenge. A dark comedy in German with English subtitles.
DIRECTOR: Win Brooks
GENRE: Horror, Comedy, Fantastic
DIRECTOR'S BIO: Raised near Washington DC, now based in Los Angeles, Win applies his unique aesthetic to commercials, fashion film, narratives and music videos. Alongside commissions, he is currently producing his next film, writing his fourth feature script and running a boutique menswear brand.
RED LIGHT GREEN LIGHT (USA)
SYNOPSIS: A man plays the game of his life against a monster who moves when he is not looking.
RATINGS GUIDE: Violence, Strong Language, Intense Imagery
DIRECTOR: Will & Joseph Martinez
GENRE: Horror, The Beyond
DIRECTOR'S BIO: Will and Joseph Martinez are identical twins, known for their award-winning short horror films and podcast, 'Deadtime Stories.' Will is a Walt Disney Imagineer and Joseph has written for Marvel TV.
RENTAL (USA)
SYNOPSIS: A woman rents out her camera but when she gets it back she discovers something strangely familiar about the footage.
RATINGS GUIDE: Language, Intense Imagery
DIRECTOR: Jake Bradbury
DIRECTOR'S BIO: Jake Bradbury is a director/writer living in Los Angeles. He has honed his skill by creating over 60 short films, in every genre, that have won numerous awards; including best thriller and best director for his short film, Darknet, from IFS fest. His most recent project is 20th Century Faux; 16 short films shot in 16 days, all about life in LA, both real and imagined. The short films premiered on IndieWire and got write-ups in Filmmaker Magazine and No Film School.
RIDE COMPLETE (USA)
SYNOPSIS: After a late night of dropping off drunk passengers, a driver is tormented by someone or something that wants her last ride of the night, to be her final night alive.
RATINGS GUIDE: Mild Language, Intense Imagery
DIRECTOR: Timothy Thompson
PREMIERE STATUS: W0rld Premiere
DIRECTOR'S BIO: Tim got his start directing music videos for artists including "Weird Al" Yankovic, Reel Big Fish, and MC Lars. He continues to write, direct, produce, and edit projects in a multitude of genres, especially his favorite: horror.
ROUGHNECK (USA)
SYNOPSIS: Roughneck is a mind-bending exploration of memory and consciousness. In the near future, mankind lives in a world where advanced technology removes negative emotions from the human experience and replaces them with a vision of a perfect human existence.
RATINGS GUIDE: Violence, Language
DIRECTOR: Andrew Hardaway
DIRECTOR'SBIO: Andrew is an award-winning commercial director with over 20 years of experience in film and TV. His commercials have been highlighted at Cannes in the Best New Director review, at the New Director Showcase at the Clios, the Art Director's Club Europe, Luerzers Archive, Shoot Magazine, Adweek, Campaign Asia, and many other creative reviews.
ROUTINE (USA)
SYNOPSIS: During a mysterious pandemic, Cassie's quarantine life has turned into a routine, until she realizes she's out of coffee. And she's determined to get her cup of joe, even if she must face the horrors of the outside world – because "she'd kill for a cup of coffee."
DIRECTOR: Russell Emanuel
DIRECTOR'S BIO: Russ Emanuel is an award-winning American director, producer, and independent filmmaker, having directed such actors as John Heard, Robert Picardo, Vincent Pastore, Glynnis O'Connor, Hallie Kate Eisenberg, Jeremy London, Ryan Hurst, William Devane, Marina Sirtis, Sean Kenney, Armin Shimerman, and Gary Graham. He grew up in both Japan and the United States and graduated from U.S.C. to study Cinema-Television. He founded Russem Productions in 2002 to promote his films including GIRL WITH GUN (2005) and documentary RESTORATION OF PARADISE (2014). Presently, WISPER (2020) marks Emanuel's fifth foray into feature filmmaking, after directing P.J. (2007), CHASING THE GREEN (2009), THE LEGENDS OF NETHIAH (2012), and OCCUPANTS (2015).
More FilmQuest 2020 Films
ESLUNA: THE CROWN OF BABYLON
SHORT FILMS (A-B) 2021
SHORT FILMS (C – E) 2021


text:
\subsubsection*{\bibname}}

\usepackage{xcolor}
\usepackage{amsmath,amssymb,amsthm,mathrsfs,url,array}
\usepackage{graphicx}
\usepackage{subfigure}
\usepackage{wrapfig}
\usepackage{appendix}
\usepackage{multirow}
\usepackage{makecell}
\usepackage{diagbox}
\usepackage[ruled,linesnumbered]{algorithm2e}
\newtheorem{Def}{Definition}
\newtheorem{Th}{Theorem}
\newtheorem{Co}{Corollary}
\newtheorem{Lm}{Lemma}
\newtheorem{Prop}{Proposition}
\allowdisplaybreaks[4]

\newcommand{\xyx}[1]{\textcolor{red}{[XYX]: #1}}
\newcommand{\fan}[1]{\textcolor{blue}{[Fan]: #1}}

\begin{document}

\onecolumn
\aistatstitle{Provable Constrained Stochastic Convex Optimization \\with XOR-Projected Gradient Descent}

\section*{Appendix}

\section{XOR-Sampling for the Weighted Case}\label{app:weighted_case}
The text here provides a synopsis for the approach in \cite{ermon2013embed}. We still encourage the readers to read the original text for a better explanation.
Let $w(\theta), p(\theta)$ and $Z$ as defined before, the high-level idea of XOR-Sampling is to first dicretize $w(\theta)$ to $w'(\theta)$ as in Definition \ref{def:discretize}, followed by embedding the weighted $w'(\theta)$  to  the unweighted space $\Delta_w$. Finally, XOR-sampling uses counting based on hashing and randomization to  sample uniformly from $\Delta_w$.

\begin{Def}\label{def:discretize}
Assume $w(\theta)$ has both upper and lower bound, namely, $M=\max_{\theta} w(\theta)$ and $m=\min_{\theta} w(\theta)$. Let $b\geq 1, \epsilon>0, r=2^b/(2^b-1)$ and $l=\lceil \log_r(2^n/\epsilon)\rceil$. Partition the configurations into the following weight based disjoint buckets: $\mathcal{B}_i=\{\theta|w(\theta)\in(\frac{M}{r^{i+1}}, \frac{M}{r^{i}}]\}, i=0,\ldots, l-1$ and $\mathcal{B}_l=\{\theta|w(\theta)\in(0,\frac{M}{r^l}]\}$. The discretized weight function $w': \{0,1\}^n\rightarrow\mathbb{R}^+$ is defined as follows: $w'(\theta)=\frac{M}{r^{i+1}}$ if $\theta\in\mathcal{B}_i, i=0,\ldots, l-1$ and $w'(\theta)=0$ if $\theta\in\mathcal{B}_l$. This leads to the corresponding
discretized probability distribution $p'(\theta)=w'(\theta)/Z'$ where $Z'$ is the normalization constant of $w'(\theta)$.
\end{Def}

For the weighted case, the goal of XOR-sampling is to guarantee that the probability of sampling one $\theta$ is proportional to the unnormalized density (up to a multiplicative constant). By Definition \ref{def:discretize}, we obtain a distribution $p'(x)$ which satisfying $\frac{1}{\rho}p(x)\leq p'(x)\leq \rho p(x)$ where $\rho=\frac{r^2}{1-\epsilon}$. Then, XOR-sampling implements a horizontal slice technique to transform a weighted problem into an unweighted one. For the easiness of illustration, we denote $M'=\max_{\theta}w'(\theta)$ and $m'$ as the smallest non-zero value of $w'(\theta)$. Then consider the simple case where $b=1$ and $r=2$, where we have $M'=2^{l-1} m'$. Let $\delta=(\delta_0, \ldots, \delta_{l-2})^T\in\{0,1\}^{l-1}$ be a binary vector of length $l-1$, XOR-sampling samples $(\theta, \delta)$ uniformly at random from the following set $\Delta_w$ using the unweighted version of sampling based on hashing and randomization:
\begin{align}
    \Delta_w=\{(\theta,\delta): w'(\theta)\leq 2^{i+1}m'\Rightarrow\delta_i=0\}.
\end{align}
If we sample $(\theta,\delta)$ uniformly at random from $\Delta_w$ and then only return $\theta$, it can be proved that the probability of sampling $\theta$ from $w'(\theta)$ is proportional to $m'2^{i-1}$ when $w(\theta)$ is sandwiched between $m'2^{i-1}$ and $m'2^i$. Therefore, this technique leads to the constant approximation guarantee of XOR-Sampling.
The precise statement of the guarantee is in Theorem 2. For general case of $b$ and $r$, please refer to \cite{ermon2013embed}.

\noindent\textbf{Setting $\epsilon\eta_{\phi}$ to Zero}~~~~
In Definition \ref{def:discretize} we can make $b$ larger and $\epsilon$ smaller enough, then there will be a possibly large but finite value of $l$ such that $\frac{M}{r^l}$ is smaller than $m$ , which leads $\mathcal{B}_l$ to be empty and $\epsilon\eta_{\phi}$ to be  zero.

\section{Proofs}\label{app:proofs}
\subsection{Proof of Lemma 1}
We define two functions $g_k^+=\max\{g_k,\mathbf{0}\}$ and $g_k^-=\min\{g_k,\mathbf{0}\}$ where $\mathbf{0}$ is a vector of all 0 which has the same dimension as $g_k$. We have $g_k=g_k^+ + g_k^-$. We define both $\nabla f(x_k)^+$ and $\nabla f(x_k)^-$ in the similar way. Then Lemma 1 gives the new bounds of two terms assuming the constant bound on the gradient, which are essential to the proof of convergence rate. The proof of Lemma 1 is as follows:

\begin{proof} (Lemma 1)
Since we have the constant bound that
\begin{align}
    \frac{1}{c}\nabla f(x_k)^+ & \leq \mathbb{E}[g_k^+]\leq c\nabla f(x_k)^+.\label{eq:pos1}\\
    c\nabla f(x_k)^- & \leq \mathbb{E}[g_k^-]\leq \frac{1}{c}\nabla f(x_k)^-.\label{eq:neg1}
\end{align}
and because of $g_k^+\geq \mathbf{0}$ and $g_k^-\leq \mathbf{0}$ we can obtain
\begin{align*}
     \frac{1}{c}||\mathbb{E}[g_k^+]||_2^2&=\frac{1}{c}\langle \mathbb{E}[g_k^+], \mathbb{E}[g_k^+]\rangle \leq \langle\nabla f(x_k)^+, \mathbb{E}[g_k^+]\rangle \\
     &\leq c\langle \mathbb{E}[g_k^+], \mathbb{E}[g_k^+]\rangle = c||\mathbb{E}[g_k^+]||_2^2.\\
     \frac{1}{c}||\mathbb{E}[g_k^-]||_2^2&=\frac{1}{c}\langle \mathbb{E}[g_k^-], \mathbb{E}[g_k^-]\rangle \leq \langle\nabla f(x_k)^-, \mathbb{E}[g_k^-]\rangle\\
     &\leq c\langle \mathbb{E}[g_k^-], \mathbb{E}[g_k^-]\rangle = c||\mathbb{E}[g_k^-]||_2^2.
\end{align*}
which exactly means
\begin{align*}
     \frac{1}{c} ||\mathbb{E}[g_k]||_2^2 &\leq \langle\nabla f(x_k), \mathbb{E}[g_k]\rangle  \leq c||\mathbb{E}[g_k]||_2^2.
\end{align*}
To prove the second inequality, we need to take advantage of the convexity of $f$. Denote $[x_k-x^*]^+=\max\{x_k-x^*,\textbf{0}\}$ and $[x_k-x^*]^-=\min\{x_k-x^*,\textbf{0}\}$, we know $x_k-x^*=[x_k-x^*]^+ + [x_k-x^*]^-$. In addition, because $f$ is convex, the index set of non-zero entries of $[x_k-x^*]^+$ and $\nabla f(x_k)^+$ is the same. The index set of non-zero entries of $[x_k-x^*]^-$ and $\nabla f(x_k)^-$ is also the same.
In addition, because of Equation~\ref{eq:pos1} and \ref{eq:neg1}, the index set of non-zero entries of $\mathbb{E}[g_k^+]$ ($\mathbb{E}[g_k^-]$) is the same with
$\nabla f(x_k)^+$ ($\nabla f(x_k)^-$).
Combining these facts with Equations \ref{eq:pos1} and \ref{eq:neg1}, we have
\begin{align*}
    \frac{1}{c}\langle\mathbb{E}[g_k^+],[x_k-x^*]^+\rangle  &\leq  \langle\nabla f(x_k)^+,[x_k-x^*]^+\rangle\\
    &\leq c\langle\mathbb{E}[g_k^+],[x_k-x^*]^+\rangle.\\
    \frac{1}{c}\langle\mathbb{E}[g_k^-],[x_k -x^*]^-\rangle  &\leq  \langle\nabla f(x_k)^-,[x_k-x^*]^-\rangle \\
    &\leq c\langle\mathbb{E}[g_k^-],[x_k-x^*]^-\rangle.
\end{align*}
Combining these two equations, we have
\begin{align*}
    \frac{1}{c}\langle\mathbb{E}[g_k],x_k-x^*\rangle  &\leq  \langle\nabla f(x_k),x_k-x^*\rangle  \leq c\langle\mathbb{E}[g_k],x_k-x^*\rangle.
\end{align*}
This completes the proof.
\end{proof}

\subsection{Proof of Theorem 4}\label{app:proof_main}
\begin{Th}\label{Th:main}
(Main) Let $b,\epsilon,l,\delta,P,\alpha,\rho,\kappa$ and $\mathcal{B}_l$ be as in section \ref{app:weighted_case} in appendix, function $f(x,\theta): \mathbb{R}^d\times\{0,1\}^n\rightarrow \mathbb{R}$ be a $L$-smooth convex function w.r.t. $x$. Denote $OPT=\min_x \mathbb{E}_{\theta\sim Pr(\theta)}f(x,\theta)$ as the global optimum.
Let $\sigma^2=\max_x\{Var(\nabla_x f(x,\theta))\}$ and $\varepsilon^2=\max_x\{||\mathbb{E}[\nabla_x f(x, \theta)]||_2^2\}$.
For any $1\leq\rho\kappa\leq\sqrt{2}$, step size $t\leq \frac{2-\rho^2\kappa^2}{L\rho\kappa}$ and sample size $N\geq1$, $\overline{x_K}$ is the output of XOR-SGD and $\mbox{obj} = \mathbb{E}_{\theta}[f(\overline{x_K}, \theta)]$ is the objective function value at $\overline{x_K}$. We have:
\begin{align}\label{eq:main}
    \mathbb{E}_{\overline{x_K}}[\mbox{obj}] - OPT
     &\leq\frac{\rho\kappa||x_0-x^*||_2^2}{2tK}+\frac{t(\sigma^2+\varepsilon^2)}{N}.

\end{align}
\end{Th}

\begin{proof}(Theorem 4)
Since we use $N$ samples at each iteration, we have $\overline{g_k}=\frac{1}{N}\sum_{i=1}^Ng_k^i$ and $\mathbb{E}[\overline{g_k}]=\mathbb{E}[g_k^i]$.
In each iteration $k$ we can adjust the parameters in XOR-Sampling to make the tail $\epsilon\eta_{\phi}$ zero, then for each sample $g_k^i$ we can obtain from Theorem 2 that
\begin{align}
    \frac{1}{\rho\kappa} \mathbb{E}_\theta [\nabla f(x_k, \theta)]^+ &\leq \mathbb{E}[g_k^{i+}]\leq \rho\kappa\mathbb{E}_\theta [\nabla f(x_k, \theta)]^+.\label{eq:pos2}\\
    \rho\kappa \mathbb{E}_\theta [\nabla f(x_k, \theta)]^- &\leq \mathbb{E}[g_k^{i-}]\leq  \frac{1}{\rho\kappa}\mathbb{E}_\theta [\nabla f(x_k, \theta)]^-.\label{eq:neg2}
\end{align}
The variance of each sample $g_k^i$ can also be bounded by
\begin{align*}
    &Var(g_k^i) \\
    &= \mathbb{E}_{\theta' \sim p'(\theta')} [||\nabla f(x_k, \theta')||_2^2] - ||\mathbb{E}_{\theta' \sim p'(\theta')} [\nabla f(x_k, \theta')]||_2^2,\\
    &\leq \rho\kappa\mathbb{E}_{\theta \sim p(\theta)} [||\nabla f(x_k, \theta)||_2^2],\\
    &= \rho\kappa (Var(\nabla f(x_k,\theta)) + ||\mathbb{E}_{\theta \sim p(\theta)} [\nabla f(x_k, \theta)]||_2^2),\\
    &\leq \rho\kappa(\sigma^2 +\varepsilon^2).
\end{align*}
Denote $\overline{g_k}^+=\max\{\overline{g_k},\textbf{0}\}$ and $\overline{g_k}^-=\min\{\overline{g_k},\textbf{0}\}$.
Clearly, $g_k^{i+} \geq 0$ and $g_k^{i-} \leq 0$. Moreover,
for a given dimension, either $g_k^{i+}=0$ for that dimension or $g_k^{i-}=0$.
Evaluating $\overline{g_k}$ dimension by dimension, we can see that
$\overline{g_k}^+=\frac{1}{N}\sum_{i=1}^N g_k^{i+}$ and $\overline{g_k}^-=\frac{1}{N}\sum_{i=1}^N g_k^{i-}$.
Combined with Equation~\ref{eq:pos2} and \ref{eq:neg2}, we know
\begin{align*}
    \frac{1}{\rho\kappa} \mathbb{E}_\theta [\nabla f(x_k, \theta)]^+ &\leq \mathbb{E}[\overline{g_k}^+]\leq \rho\kappa\mathbb{E}_\theta [\nabla f(x_k, \theta)]^+.\\
    \rho\kappa \mathbb{E}_\theta [\nabla f(x_k, \theta)]^- &\leq \mathbb{E}[\overline{g_k}^-]\leq  \frac{1}{\rho\kappa}\mathbb{E}_\theta [\nabla f(x_k, \theta)]^-.
\end{align*}

Because $\mathbb{E}[\overline{g_k}]=\mathbb{E}[g_k^i]$, we also have
\begin{align*}
    Var(\overline{g_k})=\frac{1}{N^2}Var(\sum_{i=1}^Ng_k^i)=\frac{Var(g_k^i)}{N}.
\end{align*}
Then the variance of $\overline{g_k}$ can be bounded as
\begin{align*}
    Var(\overline{g_k})&\leq \frac{\rho\kappa(\sigma^2+\varepsilon^2)}{N}.
\end{align*}

Therefore, we can then apply Theorem 3 to get the result in equation 5.
\begin{align*}
     &\mathbb{E}_{\overline{x_K}}[\mathbb{E}_{\theta}[f(\overline{x_K}, \theta)]]  -\mathbb{E}_{\theta}[f(x^*,\theta)]\\
     &\leq \frac{\rho\kappa||x_0-x^*||_2^2}{2tK}+\frac{t\max_k\{Var(\overline{g_k})\}}{\rho\kappa},\\
     &\leq\frac{\rho\kappa||x_0-x^*||_2^2}{2tK}+\frac{t(\sigma^2+\varepsilon^2)}{N}.
\end{align*}
which can also be written as
\begin{align}
    \mathbb{E}_{\overline{x_K}}[\mbox{obj}] - OPT
     &\leq\frac{\rho\kappa||x_0-x^*||_2^2}{2tK}+\frac{t(\sigma^2+\varepsilon^2)}{N}.
\end{align}
This completes the proof.
\end{proof}

\section{Experiments}\label{app_exp}
We evaluate our XOR-SGD algorithm on the inventory management \cite{ziukov2016literature,shapiro2007tutorial} and the network design problems \cite{sheldon2012maximizing,WuXSG17XORSampling,xiaojian2016}.
For each setting of both applications, to produce a sample, Gibbs sampling first takes 100 steps to burn in, and then draws samples every 30 steps. We fix the iteration step of both BP and BPChain as $20$, which is enough for BP to converge.
We allow SGD with Gibbs sampling, BP and BPChain to draw more samples than XOR-SGD for a fair comparison.
All experiments were conducted using single core architectures on Intel Xeon Gold 6126 2.60GHz machines with 96GB RAM and a wall-time limit of $10$ hours.
For both applications, we use MRF as probabilistic models for $Pr(\theta)$, which can be seen in the next section.
For a fair comparison, once a solution $x$ is generated by
either algorithm, we use an exact weighted counter ACE \cite{barton2016ace} to evaluate $\mathbb{E}_{\theta\sim Pr(\theta)} f(x, \theta)$ exactly. All objective values reported here are from ACE.

\subsection{Settings of Stochastic Inventory Management}\label{app:exp_setting_inventory}
Taking into account of the storage constraint, the original problem is equivalent to the following problem:
\begin{align}\label{eq:inventory_dual}
    \min_{x\geq 0}\max_{\mu\geq 0}\mathbb{E}_{d\sim Pr(d)}[G(x,d)]+\mu(w^{T}x-X).
\end{align}

For inventory management problem, we assume each $d_i$ can take two different values, one corresponding to the high demand one corresponding to the low demand. Then, we introduce a new vector $\theta$ where $\theta_i=1$ means $d_i$ is the high value while $\theta_i=0$ otherwise.
In the experiment we range $n$ from 10 to 100 increased by a step size of 10 and draw 10 instances for each setting. Under each setting, we draw every $c_i$ uniformly from $(0,5]$, $h_i$ uniformly from $(0,10]$, sample $s_i$ uniformly drawn from $(0,10]$ and let $b_i=c_i+s_i$.
The two values of each $d_i$ are also uniformly drawn from $(0,10]$.
We model $Pr(\theta)$ as a MRF with several cliques. The variables in each clique are highly correlated with each other.
For a problem with $n$ products, we draw the number of cliques uniformly from $[n,2n]$. The domain size of each clique $\phi_{\alpha}$ is chosen from the range of $[1,6]$ at random. The potential function of a clique  involving $l$ variables is in the form of a table of size $2^l$.
The $i$-th entry of this table, denoted as $v_i$, is modeled as $v_i=v_{i1}+v_{i2}v_{i3}$, where $v_{i1}$ is uniformly drawn from $(0,1)$, $v_3$ uniformly from $(10,1000)$ and binary variable $v_{i2}$ uniformly randomly drawn from $\{0,1\}$.
Each storage requirement $w_i$ is drawn from $(0,10]$ uniformly at random. The largest storage limit $X$ is set to be $5n$. We also evaluate our method given different percentages of the largest storage limit, which is shown in Figure 2 (middle).
In the SGD algorithm, $x$ is initialized with the absolute value of a Gaussian random variable from $\mathcal{N}(5,3)$ to ensure it is non-negative.

\subsection{Settings of Stochastic Network Design}\label{app:exp_setting_network}
The task in equation 8 is equivalent to solving the following problem:
\begin{align}\label{eq:network_dual}
    \min_{\Delta g\geq 0}\max_{\mu\geq 0}~\mathbb{E}_{\theta\sim Pr(\theta)}[\overline{C}(g+\Delta g, \theta)]
    +\mu(\sum_{e\in E} c_e \Delta g_e- B).

\end{align}
Because of the convexity of $\overline{C}(g+\Delta g, \theta)$ and strong duality, both problems have the same optimal solution.

We test our algorithm on a real-world problem, the so-called Flood Preparation problem for the emergency medical services (EMS) on road networks \cite{xiaojian2016}. The problem setup, including the graph structure and the definition of $Pr(\theta)$, are the same as that in \cite{xiaojian2016}.
The original network is unweighted, hence we set the initial conductance value for each edge as 1.
$c_e$ is initialized uniformly from the range $(0,10)$.
The largest budget size $B$ is $1000$. We evaluate our method varying the percentage allowed of the largest budget size, which is shown in Figure 3 (middle).
In the experiment, each entry of $\Delta g$ is initialized with the absolute value of a Gaussian random variable from $\mathcal{N}(0,1)$. Total number of SGD iterations is 2000, while not all algorithms can complete all 2000 iterations within the time limit of 10 hours.
The experimental results reported in the plots are based on the best solutions found by each algorithm within the time limit.
Learning rate $t$ is $1$ at first and divided by $10$ after 20 iterations, further by $10$ after 100 iterations. Parameters in XOR-Sampling are set to be the same as in the inventory management problem.

\section{Extension to the Constrained Case}\label{app:constrain_XOR-SGD}

In this part, we are able to quantify the convergence speed of algorithm \ref{alg:constrain_XOR-SGD} to the optimum if the problem only contains equality constraints.
In this case, we solve the problem $\min_x\max_{\lambda} F(x,\lambda)$ with the following augmented Lagrangian function
\begin{align}\label{eq:minmax_linear}
    F(x,\lambda)= \mathbb{E}_{\theta}[f(x,\theta)]+\lambda^T(Ax+b)+\frac{\beta}{2}||Ax+b||^2
\end{align}
where $A\in \mathbb{R}^{m\times n}$ is a full-rank matrix and $b$ is a vector, indicating the linear equality constraints. $\beta$ is a hyperparameter, which does not change in the optimization process.
See Corollary \ref{Co:primal_dual}. Our proof is extended from \cite{ouyang2013stochastic} and \cite{alghunaim2020linear}.

For the analysis below, we consider an alternating direction algorithm, and assume that
$M$ is large enough for the algorithm to find the optimal value $x_{k+1}$ in the $k-$th iteration.  in algorithm \ref{alg:constrain_XOR-SGD}
This version of the alternating optimization algorithm becomes the commonly known primal-dual gradient method.
We can prove the convergence rate of this algorithm when only equality constraints are added. Specifically,
Let $\sigma_i(A)$ be its $i$-th largest singular value, and let $\sigma_{\max}(A)=\sigma_1(A)$ and $\sigma_{\min}(A)=\sigma_{\min\{m,n\}}(A)$ be the largest and the smallest non-zero singular values of $A$, respectively. We also use $f(x)$ to represent $\mathbb{E}_{\theta}[f(x,\theta)]$ for short.
In practice we update $x$ in the $k-$th iteration using an approximated augmented Lagrangian:
\begin{align}\label{eq:approx-x}
    L_{k}(x,\lambda)=&f(x_k)+f'(x_k,\theta_{k+1})x+\lambda^T(Ax+b)\notag\\
    &+\frac{\beta}{2}||Ax+b||^2+\frac{||x-x_k||^2}{2\eta_{k+1}}
\end{align}
where we replace $f(x)$ with a first-order approximation of $f(x,\theta_{k+1})$, and add a $l_2-$norm prox-function scaled by a time-varying step size $\eta_{k+1}$. Then we have the following theorem:

\begin{Th}\label{Th:primal-dual}
In the setting of Algorithm \ref{alg:constrain_XOR-SGD} to solve problem in equation \ref{eq:minmax_linear} with only linear equality constraints, if we update $x$ according to equation \ref{eq:approx-x}, then Algorithm exhibits a rate of $O(\frac{1}{\sqrt{K}})$ of convergence in terms of the objective value. Specifically, denote $x^*$ the optimal value of $x$, let $\max_x\mathbb{E}[||\nabla f(x,\theta)||^2]\leq M^2$, $D_{X}=sup_{x_a,x_b\in \mathcal{X}}||x_a-x_b||$, and learning rate $\eta_k=\frac{D_{X}}{M\sqrt{2k}}$ for all $k\geq 1$.
Define $M(K)=\frac{\sqrt{2}\rho\kappa D_{X}M}{\sqrt{K}}+\frac{\tau^2}{2\beta K}$, where $\rho\kappa$ is the constant approximation of gradients. Then for $obj=\mathbb{E}_{\theta}[f(\overline{x_K},\theta)]$, $OPT=\mathbb{E}_{\theta}[f(x^*,\theta)]$ and $\forall \tau>0$, we have
\begin{align}\label{eq:primal-dual}
    \mathbb{E}_x[obj-OPT+\tau||A\overline{x_K}+b||^2]\leq M(K)
\end{align}
\end{Th}
The proof of Theorem \ref{Th:primal-dual} is based on two lemmas. We will start with the following simple lemma,
which is a very useful result by implementing Bregman divergence as a prox-function in proximal methods.
\begin{Lm}\label{Lm:1}
Let $f(x):\mathcal{X}\rightarrow \mathbb{R}$ be a convex differentiable function with gradient $g$. Let scalar $s\geq 0$. For any vector $u$ and $v$, denote their Bregman divergence as $D(u,v)=\omega(u)-\omega(v)-\langle\nabla\omega(v),u-v\rangle$ for a differentiable function $\omega(\cdot)$. If $u\in\mathcal{X}$, and
\begin{align}
    x^*=\text{argmin}_{x\in\mathcal{X}} f(x)+sD(x,u),
\end{align}
then,
\begin{align*}
    \langle g(x^*), x^*-x\rangle\leq s[D(x,u)-D(x,x^*)-D(x^*,u)].
\end{align*}
\end{Lm}
\begin{proof} (Lemma \ref{Lm:1})~~
The optimality condition implies
\begin{align*}
    \langle g(x^*)+s\nabla D(x^*,u), x^*-x\rangle \geq 0, ~~~\forall x\in\mathcal{X}
\end{align*}
which is equal to
\begin{align*}
     \langle g(x^*), x^*-x\rangle\leq& s\langle \nabla D(x^*,u), x-x^*\rangle\\
     =& s\langle \nabla \omega(x^*)-\nabla\omega(u), x-x^*\rangle\\
     =& s[D(x,u)-D(x,x^*)-D(x^*,u)].
\end{align*}
This completes the proof.
\end{proof}
Utilizing the Lemma \ref{Lm:1}, we are able to obtain an upper bound of the variation of the Lagrangian function and its first order approximation based on each iteration points, which is shown in Lemma \ref{Lm:2}.
\begin{Lm}\label{Lm:2}
Let $w=(x,\lambda)$, $F(w)=(A^T\lambda, Ax+b)$ and $\delta_{k}=f'(x_{k-1},\theta_k)-f'(x_{k-1})$, then for $\forall w\in\mathcal{W}$ and $k\geq 0$ we have
\begin{align*}
    &f(x_k)-f(x)+(w_{k+1}-w)^TF(w_{k+1})\leq \rho\kappa \langle \delta_{k+1}, x-x_k \rangle\\
    &+\frac{\eta_{k+1}\rho\kappa||f'(x_k,\theta_{k+1})||^2}{2}+\frac{\rho\kappa(||x_k-x||^2-||x_{k+1}-x||^2)}{2\eta_{k+1}} \\
    &+\frac{1}{2\beta}(||\lambda-\lambda_k||^2-||\lambda-\lambda_{k+1}||^2)
\end{align*}
\end{Lm}

\begin{proof} (Lemma \ref{Lm:2})~~
Due to the convexity of $f$ we have
\begin{align*}
    f(x_k)-f(x)&\leq \langle f'(x_k),x_k-x \rangle\leq \rho\kappa(\langle f'(x_k,\theta_{k+1}),x_{k+1}-x \rangle\\
    &+ \langle \delta_{k+1},x-x_k \rangle + \langle f'(x_k, \theta_{k+1}),x_k-x_{k+1} \rangle)
\end{align*}
Applying Lemma \ref{Lm:1} to equation \ref{eq:approx-x} and taking $D(u,v)=\frac{1}{2}||v-u||^2$, we have
\begin{align*}
    &\langle f'(x_k,\theta_{k+1}) + A^T[\beta(Ax_{k+1}+b)-\lambda_{k}],x_{k+1}-x \rangle\\
    &\leq \frac{\rho\kappa}{2\eta_{k+1}}(||x_k-x||^2-||x_{k+1}-x||^2-||x_{k}-x_{k+1}||^2)
\end{align*}
Combining the above two inequalities we have
\begin{align*}
    &f(x_k)-f(x)+\langle x_{k+1}-x,A^T\lambda_{k+1}  \rangle\\
    \leq& \rho\kappa\langle f'(x_k,\theta_{k+1}),x_{k+1}-x \rangle + \rho\kappa\langle \delta_{k+1},x-x_k \rangle\\
    &+ \frac{1}{2\beta}||\lambda_k-\lambda_{k+1}||^2+ \rho\kappa\langle f'(x_k, \theta_{k+1}),x_k-x_{k+1} \rangle\\
    &+ \langle x_{k+1}-x, A^T[\beta(Ax_{k+1}+b)-\lambda_{k}] \rangle\\
    \leq& \frac{\rho\kappa}{2\eta_{k+1}}(||x_k-x||^2-||x_{k+1}-x||^2-||x_{k}-x_{k+1}||^2)\\
    &+ \rho\kappa\langle \delta_{k+1},x-x_k \rangle + \rho\kappa\langle f'(x_k, \theta_{k+1}),x_k-x_{k+1} \rangle\\
    &+ \frac{1}{2\beta}||\lambda_k-\lambda_{k+1}||^2
\end{align*}
For the last term, we have
\begin{align*}
    &\langle f'(x_k, \theta_{k+1}),x_k-x_{k+1} \rangle\\
    \leq& \frac{\eta_{k+1}||f'(x_k,\theta_{k+1})||^2}{2} + \frac{||x_k-x_{k+1}||^2}{2\eta_{k+1}}
\end{align*}
where the last step is due to Young's inequality. Therefore, we have
\begin{align*}
    &f(x_k)-f(x)+\langle x_{k+1}-x,A^T\lambda_{k+1}  \rangle\\
    \leq& \frac{\rho\kappa}{2\eta_{k+1}}(||x_k-x||^2-||x_{k+1}-x||^2)+ \frac{1}{2\beta}||\lambda_k-\lambda_{k+1}||^2\\
    &+\frac{\eta_{k+1}\rho\kappa||f'(x_k,\theta_{k+1})||^2}{2} + \rho\kappa\langle \delta_{k+1},x-x_k \rangle
\end{align*}
For the optimization of $\lambda$, we have
\begin{align*}
    &\langle \lambda_{k+1}-\lambda, Ax_{k+1}+b \rangle=\frac{1}{\beta}\langle \lambda_{k+1}-\lambda, \lambda_{k}-\lambda_{k+1} \rangle\\
    =&\frac{1}{2\beta}(||\lambda-\lambda_k||^2-||\lambda-\lambda_{k+1}||^2-||\lambda_k-\lambda_{k+1}||^2)
\end{align*}
Taking the summation of the inequalities above, we obtain the desired result.
\end{proof}

Then, we are ready to prove Theorem \ref{Th:primal-dual}.
\begin{proof}~~(Theorem \ref{Th:primal-dual})~~
Since $f$ is convex and $F(w)$ is monotonic. we have
\begin{align*}
    &f(\overline{x_{K}})-f(x)+(\overline{w_K}-w)^TF(\overline{w_K})\\
    \leq& \frac{1}{K}\sum_{k=1}^{K}[f(x_{k-1})-f(x)+(w_k-w)^TF(w_k)]\\
    =&\frac{1}{K}\sum_{k=0}^{K-1}[f(x_{k})-f(x)+(w_{k+1}-w)^TF(w_{k+1})]
\end{align*}
Applying Lemma \ref{Lm:2} at the optimal solution $x=x^*$, we can derive that
\begin{align*}
    &f(\overline{x_{K}})-f(x^*)+(\overline{x_{K}}-x^*)^T(A^T\overline{\lambda_K})+(\overline{\lambda_K}-\lambda)^T(A\overline{x_{K}}+b)\\
    \leq& \frac{\rho\kappa}{K}\sum_{k=0}^{K-1}[ \frac{\eta_{k+1}||f'(x_k,\theta_{k+1})||^2}{2}
    +\frac{||x_k-x||^2-||x_{k+1}-x||^2}{2\eta_{k+1}}\\
    &+\langle \delta_{k+1}, x^*-x_k \rangle ] + \frac{1}{K}(\frac{\beta}{2}||Ax^*+b||^2+\frac{1}{2\beta}||\lambda-\lambda_0||^2)\\
    \leq& \frac{\rho\kappa}{K}\sum_{k=0}^{K-1}[ \frac{\eta_{k+1}||f'(x_k,\theta_{k+1})||^2}{2}+ \langle \delta_{k+1}, x^*-x_k \rangle ]\\
    &+\frac{1}{K}(\frac{\rho\kappa D_X^2}{2\eta_K}+\frac{1}{2\beta}||\lambda-\lambda_0||^2)
\end{align*}
The above inequality holds for all $\lambda\in\mathbb{R}^m$, hence also holds for the ball $\mathcal{B}_0=\{\lambda:||\lambda||\leq \tau\}$. Combing with the fact that the optimal solution must also be feasible, we have
\begin{align*}
    &\max_{\lambda\in\mathcal{B}_0}\{f(\overline{x_{K}})-f(x^*)+(\overline{x_{K}}-x^*)^T(A^T\overline{\lambda_K})\\
    &\qquad+(\overline{\lambda_K}-\lambda)^T(A\overline{x_{K}}+b)\}\\
    =&\max_{\lambda\in\mathcal{B}_0}\{f(\overline{x_{K}})-f(x^*)+ \overline{\lambda_K}^T(Ax^*+b)-\lambda^T(A\overline{x_K}+b)\}\\
    =&\max_{\lambda\in\mathcal{B}_0}\{f(\overline{x_{K}})-f(x^*)-\lambda^T(A\overline{x_K}+b) \}\\
    =&f(\overline{x_{K}})-f(x^*)+\tau||A\overline{x_K}+b||^2
\end{align*}
Taking the expectation over $x$, we have
\begin{align*}
    &\mathbb{E}[f(\overline{x_{K}})-f(x^*)+\tau||A\overline{x_K}+b||^2]\\
    \leq& \mathbb{E}[\frac{\rho\kappa}{K}\sum_{k=0}^{K-1}( \frac{\eta_{k+1}||f'(x_k,\theta_{k+1})||^2}{2}+\langle \delta_{k+1}, x^*-x_k \rangle)\\
    &+\frac{D_X^2}{2K\eta_K}] + \mathbb{E}[\max_{\lambda\in\mathcal{B}_0}\{\frac{1}{2\beta K}||\lambda-\lambda_0||^2\}]\\
    \leq& \frac{\rho\kappa}{K}(\frac{M^2}{2}\sum_{k=1}^K \eta_{k}+\frac{D_X^2}{2\eta_K})+ \frac{\tau^2}{2\beta K}\\ &+\frac{\rho\kappa}{K}\sum_{k=1}^K \mathbb{E}[\langle \delta_{k+1}, x^*-x_k \rangle]\\
    \leq& \frac{\sqrt{2}\rho\kappa D_{X}M}{\sqrt{K}}+\frac{\tau^2}{2\beta K}
\end{align*}
In the last step, we use the fact that $x_k$ is independent of $\theta_{k+1}$, hence the summation of expectation terms is zero. This completes the proof.
\end{proof}

\subsection{Proof of Corollary 1}
Corollary \ref{Co:primal_dual} can be directly obtained based on Theorem \ref{Th:primal-dual}.
From Theorem \ref{Th:primal-dual}, we can see $M(k)$ is $O(\frac{1}{\sqrt{k}})$. Therefore, we can directly see that algorithm \ref{alg:constrain_XOR-SGD} has $O(\frac{1}{\sqrt{K}})$ convergence rate towards the optimal value where $K$ is the total number of iterations.
We leave the proof to future work for convex inequality constraints. However, we showed experimentally in several real-world problems that XOR-SGD algorithm outperforms other methods when solving stochastic optimization problems dealing with convex inequality constraints.

\subsection{Stochastic Inventory Management}\label{subsec:inventory}
We first investigate our algorithm on the  stochastic inventory management problem studied in \cite{shapiro2007tutorial}.
Assuming there are $n$ materials. The demand of material $i$ is $d_i$. Let $d=(d_1, \ldots, d_n)^T$
be the demand vector.
The manager stocks $x_i$ amount of material $i$ at the beginning of the season. Each unit of material $i$ takes storage space $w_i$, and the total amount of pre-order is limited by the available storage space $X$.
At the end of the production season, demand $d$ will be revealed to
the the manager.
We assume the cost of ordering the $i$-th material is $c_i$ per unit. If the demand $d_i>x_i$, then a back order is needed, of which one unit costs $b_i\geq c_i$. Overall, the cost for back order is $b_i(d_i-x_i)$ if $d_i > x_i$, and is zero otherwise. On the other hand, if $d_i < x_i$, then a holding cost of $h_i$ per unit is incurred, leading to an additional total cost $h_i(x_i-d_i)$. Summing it up, the cost for material $i$ is $G_i = c_ix_i + b_i[d_i-x_i]^+ + h_i[x_i-d_i]^+$ where $[a]^+$ denotes the maximum of $a$ and 0. Then,
the total cost will be $G(x,d)=\sum_{i=1}^{n}G_i$. The manager want to minimize his operational cost, which translates to this problem:
\begin{align}\label{eq:inventory}
    \min_{x\geq 0}~~\mathbb{E}_{d \sim Pr(d)}[G(x,d)], \quad s.t. \quad w^T x \leq X.
\end{align}
where $G(x,d)$ is convex w.r.t. $x$.
We run the experiments varying the number of materials $n$,
the storage limit, and the number of samples we use in XOR-PGD and other methods. Parameters and experimental settings are the same as in \cite{fan2021xorsgd}.
In terms of the parameters in XOR-Sampling we fix $P=100, b=7, \epsilon=0.01$ and the others the same as in \cite{ermon2013embed} to guarantee $\rho\kappa=\sqrt{2}$. Learning rate $t$ is $0.1$ at first and divided by $10$ after $50$ iterations, then further divided by $10$ after $100$ iterations. $\eta$ is 10 at first and divided by $10$ after $50$ iterations, then further divided by $10$ after $100$ iterations. The total number of both $K$ and $M$ are set to be $200$.
However, since we run each algorithm on one single core with a wall-time limit of $10$ hours for a fair comparison, not all algorithms can complete all iterations. The plots are based on the best results found by each algorithm within the time limit.

Table \ref{tab:saving} shows that our algorithm outperforms other methods varying number of materials on the percentage reduction of the objective values of the solutions. In math form, for example for Gibbs Sampling, the metric is $(obj(\mbox{Gibbs}) - obj(\mbox{(I)XOR-PGD})) / obj(\mbox{Gibbs})$ (metrics for other approaches are analogous). The objective optimized by (I)XOR-PGD is on average 2 percent better than XOR-SGD and $10\%$ more than that optimized by other baselines. In addition, Table \ref{tab:constraints} shows that the rate of constraints satisfaction of the solutions from either XOR-PGD or (I) XOR-PGD is $10\%$ more than that of XOR-SGD even in very large searching space.
The first row in Figure \ref{fig:exp} shows the objective values of solutions varying the storage limit, and the objective values varying the number of samples with $100\%$ storage limit and 50 different materials.
We can see from the left figure that with the storage limit increasing, (I)XOR-PGD is always better than all baselines, and from the right figure that (I)XOR-PGD found better solutions with less samples than XOR-SGD. Since \cite{fan2021xorsgd} already reported that XOR-SGD is faster than the other competing approaches, here by comparing efficient sample size with XOR-SGD we conclude that (I)XOR-PGD is faster than all the other methods.

\subsection{Stochastic Network Design}\label{subsec:network}
We then consider the expected commuting time of a random walk
in network optimization  \cite{ghosh2008minimizing,McClure2016ConnectingMT,Inman2013DevelopingPF}, which is also a benchmark in \cite{fan2021xorsgd}.
Given an undirected graph $G=(V,E)$, where $|V|=m, |E|=n$.
Let $g = (g_1, \dots, g_n)^T$, and edge $e\in E$ is associated with a binary random variable $\theta_e$ that describes the state of the edge during disasters. $\theta_e=0$ means that the edge is destroyed, and 1 otherwise. Let $\theta=(\theta_1, \dots, \theta_n)$.
It will take money $c_e$ to increase one unit of $g_e$ and we have a total budget of $B$.
Then, From \cite{ghosh2008minimizing} we know the commuting time
\begin{align*}
    \overline{C}(g, \theta)=\frac{4(\mathbf{1}^Tg)}{(m-1)}\Big{(}\mathbf{Tr}(L+\mathbf{1}\mathbf{1}^T/m)^{-1}-1\Big{)}
\end{align*}
which is convex w.r.t. $g$, where $L$ is the weighted Laplacian matrix.
We would like to find the best network improvement plan under the given budget, which minimizes the expected commuting time averaged over all stochastic events to maximizes the network connectivity. Mathematically, our problem can be formulated as the following problem:
\begin{align*}
    \min_{\Delta g\geq 0}~\mathbb{E}_{\theta\sim Pr(\theta)}[\overline{C}(g+\Delta g, \theta)],
    ~ s.t. ~ \sum_{e\in E} c_e \Delta g_e\leq B.

\end{align*}
We evaluate our algorithms on the Flood Preparation problem for the emergency medical services (EMS) on road networks as studied in \cite{xiaojian2016} and test our algorithm on four benchmarks involving the weak and the strong network originally evaluated in \cite{fan2021xorsgd} varying the percentage of the largest budget size and samples size, which is shown in the bottom row of Figure \ref{fig:exp}. The largest budget size $B$ is $1000$. Total number of SGD iterations is 2000, while not all algorithms can complete all 2000 iterations within the time limit of 10 hours. Parameters in XOR-Sampling are set to be the same as in \cite{fan2021xorsgd}.

The results are similar to those for the inventory management problem, where results clearly show that (I)XOR-PGD outperforms other methods both in efficiency and in the quality of solutions.
On all of the four different type of networks (I)XOR-PGD saves on average $>3\%$ against XOR-SGD and more than $9\%$ against the other competing methods.
In addition, we would like to emphasize that (I)XOR-PGD with 40 samples already outperforms XOR-SGD with 60 samples in the right figure while finds better solutions at the same time, and even naive XOR-PGD finds better solutions than XOR-SGD given the same sample size.

The left figure in Figure 3 shows the percentage of savings between SGD with other sampling methods and XOR-SGD among all of the 4 different networks, while the middle and the right figures show the averaged commuting time with regard to different budget sizes and different number of samples, respectively. For the left and the middle figures, we let XOR-SGD take 100 samples in each iteration while SGD with other methods take 10,000. We can see from the left figure that objective optimized by XOR-SGD is at least 5\% better than that optimized by other methods for all the 4 different networks. In addition, from the middle and the right figures we know that with the increase of either budget size or the number of samples, our method can find consistently better solutions than the compared methods. In particular, from the right figure we can see even 40 samples in each iteration are enough for XOR-SGD to compete with the result from Gibbs with 20,000 samples. Meanwhile, XOR-SGD also runs faster than the compared method under this situation. In this experiment, XOR-SGD with 40 samples take 1 minutes 40 seconds per SGD iteration, while SGD with 20,000 Gibbs samples need 2.5 minutes per iteration.
Since sampling time of both BP and BPChain is no shorter than Gibbs Sampling, we thus conclude that XOR-SGD outperforms other methods both in efficiency and in the quality of solutions found.

\subsection{Improved XOR-PGD}
Although we prove that the proposed XOR-PGD has a theoretical guarantee on the convergence rate, this convergence rate of $O(\frac{\log K}{K})$ is not rather surprising. Therefore, we further improve the algorithm by selecting a more reasonable step size. By selecting $t_k=\frac{2\rho\kappa}{\mu(k+1)}$ as in Algorithm \ref{alg: improved XOR-PGD}, and compute the last output from a weigthed average ${x_K}\gets \reallywidehat{x_K}= \frac{2\sum_{k=1}^K k x_k}{K(K+1)} $,  we develop a improved algorithm of XOR-PGD named (I)XOR-PGD in Algorithm \ref{alg: improved XOR-PGD}. We prove that this (I)XOR-PGD is able to further accelerate the convergence rate to $O(\frac{1}{K})$.

\begin{Th}\label{Th:XOR_SGD_bound_constrained_improved}
Let $f:\mathbb{R}^d\rightarrow \mathbb{R}$ be a $L$-smooth and $\mu$-strongly convex function and $x^*=\arg\min_{x\in C} f(x)$, where $C$ is a convex  set of $x$. In iteration $k$, $g_k$ is the estimated gradient, i.e., $x_{k+1}=\mathbb{P}_C(x_{k}-t_kg_k)$ where $Var(g_k)\leq \sigma^2$ and $\mathbb{P}_C(x):=\arg \min_{y\in C}\frac{1}{2}\|x-y\|_2^2$ is the projection of $x$ onto $C$. If $t_k = \frac{2c}{\mu (k+1)}$ and there exists $1\leq c\leq\sqrt{2}$ s.t. $\frac{1}{c}[\nabla f(x_k)]^+ \leq \mathbb{E}[g_k^+]\leq c[\nabla f(x_k)]^+$ and $c[\nabla f(x_k)]^- \leq \mathbb{E}[g_k^-]\leq \frac{1}{c}[\nabla f(x_k)]^-$, then the convergence rate of the Improved XOR-PGD algorithm is $O(\frac{1}{K})$:
\begin{align*}
    &\mathbb{E}\left [f\left ( \reallywidehat{x_K}\right )\right ]-f(x^*) \leq \frac{2B}{\mu (K+1)},
\end{align*}
where $\reallywidehat{x_K}=\frac{2}{K(K+1)} \sum_{k=1}^K k x_k$.
\end{Th}

\begin{proof}
With $t_k=\frac{2c}{\mu (k+1)}$ and multiplying~\eqref{key_ineq} by $k+1$, we have
\begin{align*}
    &k(\mathbb{E}[f(x_k)]-f(x^*))\leq \frac{kB}{\mu (k+1)}\\& + \frac{\mu}{4} \left ( k(k-1)\mathbb{E}[\|x_{k}-x^*\|^2] - k(k+1)\mathbb{E}[\|x_{k+1}-x^*\|^2]\right )\\
    &\leq \frac{B}{\mu}  + \frac{\mu}{4}  ( k(k-1)\mathbb{E}[\|x_{k}-x^*\|^2]\\
    & \qquad ~ - k(k+1)\mathbb{E}[\|x_{k+1}-x^*\|^2] )
\end{align*}
Summing from $k=1$ to $k=K$, we have
\begin{align*}
    &\sum_{k=1}^K k(\mathbb{E}[f(x_k)]-f(x^*))\\ &\leq \frac{KB}{\mu} + \frac{\mu}{4}(0-K(K+1)\mathbb{E}[\|x_{k+1}-x^*\|^2]).
\end{align*}
Then, we have
\begin{align*}
    &\mathbb{E}\left [f\left ( \frac{2}{K(K+1)} \sum_{k=1}^K k x_k\right )\right ]-f(x^*) +\frac{\mu}{2} \mathbb{E}[\|x_{k+1}-x^*\|^2]\\ &\leq \frac{2B}{\mu (K+1)},
\end{align*}
which implies
\begin{align*}
    &\mathbb{E}\left [f\left ( \reallywidehat{x_K}\right )\right ]-f(x^*) \leq \frac{2B}{\mu (K+1)},
\end{align*}
where $\reallywidehat{x_K}=\frac{2}{K(K+1)} \sum_{k=1}^K k x_k$. Here we prove the $O(1/K)$ convergence rate.
\end{proof}

Similarly, we can get the final convergence rate of the Improved XOR-PGD as in Algorithm \ref{alg: improved XOR-PGD} by increasing the sample size from 1 to $N$.

\begin{Co}\label{improved main}
(Main) Let $\rho,\kappa$ be as before, function $f(x,\theta): \mathbb{R}^d\times\{0,1\}^n\rightarrow \mathbb{R}$ be a $L$-Lipschitz and $\mu$-strongly convex function w.r.t. $x$. Denote $OPT=\min_{x\in C} \mathbb{E}_{\theta\sim Pr(\theta)}f(x,\theta)$ as the global optimum.
Let $\sigma^2=\max_x\{Var(\nabla_x f(x,\theta))\}$ and $\varepsilon^2=\max_x\{||\mathbb{E}[\nabla_x f(x, \theta)]||_2^2\}$.
For any $1\leq\rho\kappa\leq\sqrt{2}$, step size $t\leq \frac{2\rho\kappa}{\mu (k+1)}$ and sample size $N\geq1$, $\reallywidehat{x_K}=\frac{2}{K(K+1)} \sum_{k=1}^K k x_k$ is the output of Improved XOR-PGD (algorithm \ref{alg: improved XOR-PGD}) and $\mbox{obj} = \mathbb{E}_{\theta}[f(\reallywidehat{x_K}, \theta)]$ is the objective function value at $\reallywidehat{x_K}$. We have:
\begin{align*}
    &\mathbb{E}_{\reallywidehat{x_K}}[\mbox{obj}] - OPT\\
     &\leq \left (\frac{\rho^4\kappa^4L^2}{\mu}+\frac{\rho\kappa(\sigma^2+\varepsilon^2)}{\mu N}\right )\frac{1}{K+1} .
\end{align*}
\end{Co}

We skip the proof since it is very similar to the proof of Theorem \ref{Th:main}. It should be noticed that although hard to compute, $\sigma^2$ and $\varepsilon^2$ are from the input which do not depend on the algorithm. In addition, it should be noticed that the convergence rate of our algorithm is determined by the approximation constant $\rho\kappa$ from XOR-sampling. The smaller this constant is, the lower the success rate of XOR-Sampling has. By setting proper parameter values, we can get $\rho\kappa=\sqrt{2}$. As a consequence, we can collect $N$ samples successfully by running XOR-Sampling around $40N$ times. The time complexity can be further reduced via parallel sampling. In addition, the sampling procedure is independent of the optimization step since $Pr(\theta)$ does not depend on $x$.
\subsection{Probabilistic Distribution}
The probability distribution $Pr(\theta)$ can be defined in various different forms.
We consider $Pr(\theta)$ as a graphical model specified as a factor graph with $N=|V|$ discrete random variables $\theta_i\in \Theta_i, i \in V$ where $\Theta_i=\{0,1\}$. The global random vector $\theta=[\theta_1,\theta_2,\ldots,\theta_N]$ takes value in the cartesian product $\Theta = \Theta_1 \times \Theta_2 \times \cdots \times \Theta_N$. We consider a function over $\theta \in \Theta$ as follows:
\begin{align}\label{eq:mrf}
f(\theta)=\prod_{\alpha\in \mathcal{I}} \phi_{\alpha}(\{\theta\}_{\alpha})
\end{align}
which factors into potentials $\phi_{\alpha}:\{\theta\}_{\alpha}\rightarrow \mathbb{R}^{+}$, where $\mathcal{I}$ is the set of all the cliques of the graph, $\{\theta\}_{\alpha}\subseteq V$ is a subset of variables that the factor $\phi_{\alpha}$ depends on. We consider a normalized distribution $p(\theta) = \frac{1}{Z}f(\theta)$ where $Z$, the normalization constant, also known as the partition function, is defined as $Z=\sum_{\theta} f(\theta)$. The structure of $Pr(\theta)$ or the set $\mathcal{I}$ can be built from domain knowledge and potential functions can be learned from real-world data. The focus of this paper is not on how to construct the MRF but is how we solve problem in Equation \ref{eq:sto} in general when $Pr(\theta)$ is given in the form shown in Equation \ref{eq:mrf}.

\subsection{XOR-SGD}
XOR-SGD outperforms SGD with MCMC based samplers in that it has a constant bound on the probability of drawn samples and further guarantee a constant bound between the expectation of the distribution formed by samples and the expectation of true distribution, without requiring exponentially large number of samples.
These samples are drawn by XOR-Sampling \citep{ermon2013embed}, a recently
proposed sampling scheme with a constant approximation guarantee,
which reduces the sampling problem into queries of NP oracles via
hashing and projection. Indeed, XOR-SGD requires accessing NP-oracle queries at each iteration.
Specifically, XOR-SGD is guaranteed to converge to a solution that is within a vanishing constant away from the true optimum in linear number of iterations, which is shown as Theorem \ref{Th:XOR-SGD}.

\begin{Th}\label{Th:XOR-SGD}\citep{fan2021xorsgd}
Let $\rho,\kappa$ be the constant approximation factor as in \cite{fan2021xorsgd}, function $f(x,\theta): \mathbb{R}^d\times\{0,1\}^n\rightarrow \mathbb{R}$ be a $L$-smooth convex function w.r.t. $x$. Denote $OPT=\min_x \mathbb{E}_{\theta\sim Pr(\theta)}f(x,\theta)$ as the global optimum.
Let $\sigma^2=\max_x\{Var(\nabla_x f(x,\theta))\}$ and $\varepsilon^2=\max_x\{||\mathbb{E}[\nabla_x f(x, \theta)]||_2^2\}$.
For any $1\leq\rho\kappa\leq\sqrt{2}$, step size $t\leq \frac{2-\rho^2\kappa^2}{L\rho\kappa}$ and sample size $N\geq1$, $\overline{x_K}$ is the output of XOR-SGD and $\mbox{obj} = \mathbb{E}_{\theta}[f(\overline{x_K}, \theta)]$ is the objective function value at $\overline{x_K}$. We have:
\begin{align}\label{eq:main}
    \mathbb{E}_{\overline{x_K}}[\mbox{obj}] - OPT
     &\leq\frac{\rho\kappa||x_0-x^*||_2^2}{2tK}+\frac{t(\sigma^2+\varepsilon^2)}{N}.

\end{align}
\end{Th}

Theorem 1 states that in expectation, the difference in terms of the objective function values between the output of XOR-SGD algorithm $\overline{x_K}$ and the true optimum $OPT$ is bounded
by a term that scales inversely proportional to the number of SGD iterations $K$ and a tail term $\frac{t(\sigma^2+\epsilon^2)}{N}$. Although hard to compute, both $\sigma^2$ and $\epsilon^2$ are from the input and do not depend on the algorithm. However, although the authors provide a constrained version of XOR-SGD in their paper, they are not able to give a theoretical guarantee of convergence rate of this algorithm under the constrained setting, which is known to be more intractable due to the extra constraints on the solution space.

\subsubsection*{References}}
\usepackage{mathtools}
\usepackage{booktabs}
\usepackage{tikz}

\newcommand{\swap}[3][-]{#3#1#2}

\usepackage{xcolor}
\usepackage{amsmath,amssymb,amsthm,mathrsfs,url,array}
\usepackage{booktabs}
\usepackage{tikz}
\usepackage{makecell}
\usepackage{diagbox}
\usepackage{multicol}
\usepackage{multirow}
\usepackage{graphicx}
\usepackage{subfigure}
\usepackage{appendix}
\usepackage[ruled,linesnumbered]{algorithm2e}
\newtheorem{Def}{Definition}
\newtheorem{Th}{Theorem}
\newtheorem{Co}{Corollary}
\newtheorem{Lm}{Lemma}
\usepackage{scalerel,stackengine}
\stackMath
\newcommand\reallywidehat[1]{%
\savestack{\tmpbox}{\stretchto{%
  \scaleto{%
    \scalerel*[\widthof{\ensuremath{#1}}]{\kern-.6pt\bigwedge\kern-.6pt}%
    {\rule[-\textheight/2]{1ex}{\textheight}
  }{\textheight
}{0.5ex}}%
\stackon[1pt]{#1}{\tmpbox}%
}
\newcommand{\xyx}[1]{\textcolor{red}{[XYX]: #1}}
\newcommand{\fan}[1]{\textcolor{blue}{[Fan]: #1}}

\title{Provable Constrained Stochastic Convex Optimization \\
with XOR-Projected Gradient Descent}

\author[1]{\href{mailto:<ding274@purdue.edu>?Subject=Your UAI 2022 paper}{Fan Ding}{}}
\author[2]{Yijie Wang}
\author[3]{Jianzhu Ma}
\author[1]{Yexiang Xue}
\affil[1]{%
    Computer Science Dept.\\
    Purdue University\\
    West Lafayette, Indiana, USA
}
\affil[2]{%
    Computer Science Dept.\\
    Indiana University\\
    Bloomington, Indiana, USA
  }
\affil[3]{%
    Institute for Artificial Intelligence \\
    Peking University \\
    Beijing, China
}

\begin{document}
\maketitle

\begin{abstract}
  \input{tex/abstract}
\end{abstract}

\section{INTRODUCTION}\label{sec:intro}
\input{tex/intro}

\section{PRELIMINARIES}\label{sec:prelim}
\input{tex/prelim}

\section{XOR-PROJECTED GRADIENT DESCENT}\label{sec:method}
\input{tex/method}

\section{EXPERIMENTS}\label{sec:exp}

\input{tex/exp}
\vspace{-0.3cm}
\section{CONCLUSION}\label{sec:conclusion}
\input{tex/conclusion}

\clearpage

redpajama_set_name: RedPajamaArXiv


text:
Lunch & Law Speaker Series
ChevronWatch
Nondelegation, Origination Clause, and IRS's "Curio" Power
Nov 20, 2019 | Adi Dynar, Blog
Perhaps you get a pass if you don't know that there is a federal agency called the Federal Service Impasses Panel that resolves disputes between federal agencies and federal-employee unions. But the Internal Revenue Service is not some obscure federal agency. IRS is always lurking somewhere in our wallets and pocketbooks. If you are an average American, you spend up to two hours of your eight-hour workday making money for IRS. Few would disagree with the statement that IRS has an outsized influence on all of our lives.
It is surprising, however, that very few appreciate one of the best kept secrets about IRS—Section 7805 of the Internal Revenue Code. I certainly didn't know about this provision until recently. I call it IRS's "curio" power because it is so unusual—and likely unconstitutional.
Section 7805 authorizes IRS to issue rules and regulations and make them apply retroactively from the date IRS "substantially describe[ed] the expected contents of any … proposed" regulation to the public. Let's digest that for a minute.
Say IRS publishes a bulletin on its website saying: IRS thinks there is a loophole in the statute with respect to taxing pensions and annuities. Congress is probably not going to do anything about it. So, we might issue a rule sometime in the future to close the escape hatch that taxpayers are exploiting to reduce their tax burden. That is a "substantial description" of a "proposed" regulation for purposes of Section 7805. Now, if IRS gets around to issuing a final regulation five years after they published the bulletin, they can make the new rule apply retroactively during that five-year period. That means taxpayers who relied on the loophole to reduce their tax burden are now required to cough up five years' worth of back taxes (and probably even penalties for late payment).
Keep in mind, the taxpayer is not doing anything illegal or immoral in taking advantage of an exception that Congress enacted to reduce the tax burden. IRS, predictably, frames that as a bad thing because otherwise IRS is not able to raise as much revenue as it would have had the exception not existed.
Retroactivity in IRS's hands is alarming. We could easily spend a whole day discussing the various reasons why IRS's authority to give retroactive effect to its regulations is unconstitutional. Other scholars have flagged retroactivity as an extremely dangerous tool that federal administrators use to diminish the rights and civil liberties of the people. There is, however, an additional reason why Section 7805, independent of the retroactivity problem, should be peculiarly unconstitutional, specifically because its power is wielded by IRS.
Article I, Section 7, Clause 1 of the U.S. Constitution—also called the Origination Clause—declares that "All bills for raising revenue shall originate in the House of Representatives; but the Senate may propose or concur with amendments as on other Bills." A straightforward application of this Clause should indicate the constitutional problem with a provision such as Section 7805.
If Congress enacts a statute that reduces the amount of taxes one has to pay, that decreases the "revenue" flowing into the federal treasury. When IRS, by regulation, discards that provision established by Congress, the regulation raises revenue that flows into the U.S. Treasury. But revenue-raising measures, by the plain words of the Constitution, must "originate in the House of Representatives." If, instead, IRS's rulemaking raises revenues, that very well may violate the Origination Clause.
The Origination Clause is an important non-delegation principle expressly stated in the Constitution. Only Congress, specifically the House, can originate bills for raising revenue. That is because, under the original plan of the Constitution, the people's representatives, not unelected officials, have the duty and authority to raise revenues for the operation of the federal government. The Constitution specifically withheld this authority from the Senate even. Before the ratification of the Seventeenth Amendment in 1913, the Senate represented the state governments, not the people. That this authority is withheld from a body that did not represent the people is telling. Section 7805's cession of the House's prerogative to an unelected and unaccountable federal agency has breached an important promise the Constitution made to the people. To borrow James Madison's words, a statute like Section 7805 is "the most complete and effectual weapon" to disarm "the immediate representatives of the people."
Congress should consider taking this formidable tool out of IRS's toolbox. And until it does, we should add creating awareness about Section 7805 to our list of things that government could do to downsize the impact unelected federal officials have on our lives.
Written by Adi Dynar
A Catastrophic Assault on our Civil Liberties
NCLA Defends Founder of The Federalist from Outrageous NLRB Action Instigated by Random Tweeter Who Is Not an "Aggrieved" Party Under Federal Labor Law
WATCH: NCLA Video Calls Out ATF for Rewriting Statute and Turning Law-Abiding Citizens into Criminals Overnight
NCLA Asks Court to Not Abandon Its Duty of Independent Judgment in BIA Case Under Chevron Deference
Amicus Brief: Brackeen v. Bernhardt
Adi Dynar
Caleb Kruckenberg
Ethan Beck
Gelane Diamond
Haley Connor
Harriet Hageman
Jay Schaefer
Jessop v. City of Fresno
Kara Rollins
Madeleine Case
Mark Chenoweth
Michael P. DeGrandis
Official Case Page
Peggy Little
USA v. Havis
New Civil Liberties Alliance | 1225 19th Street Northwest, Suite 450, Washington, DC 20036 | (202) 869-5210
2019 © New Civil Liberties Alliance. All Rights Reserved. Privacy Policy | Terms of Use

redpajama_set_name: RedPajamaCommonCrawl


Subaru Outback - Subaru Outback Forums > Vendors > Discount Tire > 18" Method MR502 CLEARANCE!
Discount Tire Direct (DTD) has the 18x8 5-100 ET+38 Method MR502 Rally Wheels on clearance - Bronze and Titanium finishes are in stock!
Get your set today before they are gone!!! $179.97 per wheel with FREE delivery and right now you can save an additional $50.00 instantly with the purchase of four(4)!!!
Need tires too? DTD will mount and balance your tire and wheel package for no additional charge! PM us to place an order.
Correct - this clearance pricing is for the 18x8 size only.
DTD does have the 17x8 available and a new set also qualifies for an instant $50.00 discount.


text:
Q: compare an object with a json schema and fill it with the schema default values if they are not set I'm using Ruby JSON Schema Validator to validate some of my input data, which is quite nice.
But I would like to update my input data so that it takes the default values of the schema if its values are not set.
  input = {'url' => 'http://www.google.com'}

  schema = {
    "type": "object",
    "properties": {
      "url": {
        "type": "string",
      },
      "infos":{
        "type": "object",
        "properties": {
          "content_type": {
            "type": "string",
            "default": "html",
          },
        }
      }
    }
  }

  #make some magic here to update my input with the schema

  output = {
      'url' => 'http://www.google.com',
      'infos' => {'content_type'=>'html'}
  }

How could I achieve this, knowing that the structure of the input is not the same as the one of the schema ?
There is an :insert_defaults option with the Ruby JSON Schema Validator, but I don't see a way to retrieve the filled object.
Seems that the code related to that is here.
I've also searched Google, made some attempts with deep_merge(), but since the structures to compare are not identical, I don't know how to handle this.

A: Here's what I came up with :
def defaultsFromSchema(node,nodekeys=[],datas={})
  return unless node.is_a?(Hash)

  if node.has_key?('default')
    value = node['default']
    #create hash and set deep keys
    return nodekeys.reverse.inject(value) { |a, n| { n => a } }

  else
    node.each do |k, v|
      keys = nodekeys.clone
      if k != 'properties'
        keys.push(k)
      end

      append = defaultsFromSchema(v,keys,datas)
      if append
        datas = datas.deep_merge(append)
      end

    end
  end

  datas

end

redpajama_set_name: RedPajamaStackExchange


With 13 locations, it's not hard to find a Puritan Cleaners to benefit from decades of experience. At HandCraft Cleaners, don't let that "dry clean only" tag scare you. They'll take care of it. HandCraft has been keeping Richmond's favorite clothes clean for 45 years. The family business has grown from one location on Patterson to include Henrico County and Bon Air satellites. Mary Ellen at the original location credits its success to excellent customer service, lots of return customers and referrals. She says HandCraft's wedding-gown specialist, Dan Thomas, is legendary. He's cleaned and preserved customers' heirloom dresses for years. But the friendly atmosphere keeps people coming back, Mary Ellen says, for multiple washes.


text:
UNITE HERE: France Says "Non!" to Las Vegas UFC-Style Cage Fighting
July 22, 2013 01:58 AM Eastern Daylight Time
LAS VEGAS--(BUSINESS WIRE)--The French Sports Ministry, which is headed by Valérie Fourneyron, reconfirmed recently the country's ban on mixed martial arts ("MMA"), stalling for now hopes that UFC-style cage fighting events will become legal in France.
Responding to a question from a Deputy of the National Assembly, the Sports Ministry stated on July 2: "Free Fight, or Mixed Martial Arts (MMA), takes place inside a cage and allows strikes against the opponent while on the ground. The policy of the Ministry has not changed and remains clear. The practice of MMA is not allowed and its events/shows are not permitted."
The ban was reconfirmed despite lobbying of the French government by Zuffa LLC of Las Vegas, whose Ultimate Fighting Championship ("UFC") promotes violent spectacles of "free fighting" or "cage fighting" (so-called "mixed martial arts"). Last year, UFC CEO Lorenzo Fertitta called France a "massive opportunity" and said he was "encouraged that you'll be eating croissants watching the UFC pretty soon."
Carole Bretteville, President of the Women's Committee for Federation Francaise du Sport d'Entreprise ("FFSE"), applauded the Ministry's response. "France works very hard to promote equality in all aspects of life, especially in sports," said Bretteville. "FFSE promotes sport as a unifying force, where management and employees together benefit from shared recreation activities. I was appalled to find out how UFC was lobbying in France, especially when UNITE HERE informed me how UFC has tolerated derogatory statements and attitudes against women. We cannot allow such an organization to destroy all the work we have done to promote equality through French sports. I applaud the Minister's courage to reject free fighting in France."
UNITE HERE's European Development Director Blake Harwell said: "We were not surprised. European attitudes toward such bloody displays date back centuries. Add in the anti-social issues and I'd say Zuffa and the IMMAF have a long way to go to make MMA palatable. No matter what name they call it, cage fighting still fails to meet European expectations for what counts as sport."
UNITE HERE
Blake Harwell, +44 (0) 7720-77-3025
French Sport Ministry reconfirms the country's ban on mixed martial arts ("MMA"), stalling for now hopes that UFC-style cage fighting events will become legal in France.


text:
Q: Send data to the server using ExtJs is it the write syntax ??in the params section i want to  add this field to send to the server but not working
 Ext.Ajax.request({

                url:'http://localhost:8084/org.servlet/url_servlet',
                method:'GET',

 params:{

        myname:document.getElementById('firstname').value//this is the field i want to send to the servlet

    } ,
              success: function (response){
            Ext.Msg.alert('Succesfully added ');

     },
          failure: function (){
           Ext.Msg.alert('Error in server');
    }

A: You can do it with ajax
Example Code
Ext.Ajax.request({
    url: 'page.php',
    params: {
        id: 1
    },
    success: function(response){
        var text = response.responseText;
        // process server response here
    }
});


Difference between revisions of "SUNScholar/Interoperability"
"Interoperability is a property of a product or system, whose interfaces are completely understood, to work with other products or systems, present or future, without implementation or any restrictions in access."
What "interfaces" does [http://www.dspace.org DSpace] have?
#[[SUNScholar/Submission_System|Submit items using the submission system]].
#[[SUNScholar/API|Submit items using the web API]].
#[[SUNScholar/Submission_System|Submit content using the XMLUI interface]].
#[[SUNScholar/XMLUI_Theme|Import content using the XMLUI administrative interface]].
#[[SUNScholar/Metadata/Batch_Edit|Import metadata using the XMLUI administrative interface]].
#[[SUNScholar/Export_and_Import_Artifacts/Via_Packages|Import using the packages format]].
#[[SUNScholar/Export_and_Import_Artifacts/Via_Simple_Archive_Format|Import using the simple archive format]].
#[https://wiki.duraspace.org/display/DSDOC5x/AIP+Backup+and+Restore Backup using the AIP format].
#[https://github.com/DSpace/dspace-replicate Archive content in the cloud].
#[[SUNScholar/Remote_Deposit|Submit items using the SWORD interface]].
#[[SUNScholar/XMLUI_Theme|Export/Import content using the XMLUI administrative interface]].
#[[SUNScholar/Harvesting|Harvest the content of remote collections to the local IR via the OAI interface]].
#[[SUNScholar/Export_and_Import_Artifacts/Via_Packages|Export/Import using the packages format]].
#[[SUNScholar/Export_and_Import_Artifacts/Via_Simple_Archive_Format|Export/Import using the simple archive format]].
#[[SUNScholar/Metadata/Batch_Edit|Export/Import metadata using the XMLUI batch metadata editor]].
#[https://wiki.duraspace.org/display/DSDOC5x/AIP+Backup+and+Restore Backup and restore using the AIP format].
#[[SUNScholar/XMLUI_Theme|Allow users to "download" content via the XMLUI interface]].
#[[SUNScholar/API|Allow other systems to modify content using the web API]].
#[[SUNScholar/XMLUI_Theme|Download content using the XMLUI interface]].
#[[SUNScholar/Remote_Harvest|Allow other systems to "harvest" content via the OAI interface]].
#[[SUNScholar/XMLUI_Theme|Export content using the XMLUI administrative interface]].
#[[SUNScholar/Metadata/Batch_Edit|Export metadata using the XMLUI administrative interface]].
#[[SUNScholar/Export_and_Import_Artifacts/Via_Packages|Export using the packages format]].
#[[SUNScholar/Export_and_Import_Artifacts/Via_Simple_Archive_Format|Export using the simple archive format]].
#[https://wiki.duraspace.org/display/DSDOC5x/AIP+Backup+and+Restore Restore using the AIP format].
#[https://github.com/DSpace/dspace-replicate Restore archived content from the cloud].
#[[SUNScholar/Remote_Harvest|Allow remote systems to "harvest" the content of the local IR via the OAI interface]].
DSpace has many interfaces that allow for '''content interoperability''' with other systems.
In addition DSpace is built using [[SUNScholar/Open_System|open systems]] to allow for '''technical interoperability''' with other open systems.
This page has been accessed 57,217 times.


text:
Třebušín je zámek ve stejnojmenné obci v okrese Litoměřice. Postaven byl jako renesanční tvrz ve druhé polovině šestnáctého století, ale dochovaná podoba je výsledkem barokní přestavby z doby okolo roku 1710 a mladších úprav. Od roku 1964 je chráněn jako kulturní památka. Ve druhé polovině dvacátého století v zámku bývala škola a později hotel.

Historie
První panské sídlo doložené archeologickém výzkumem na zahradě domu (dříve čp. 64) nedaleko kostela svatého Mikuláše stálo už na přelomu dvanáctého a třináctého století. Pravděpodobně se k němu váže zmínka z roku 1169, kdy se zde uvádí Bleh z Třebušína. Tvrz či dvorec zanikly nejspíše během husitských válek.

Ve druhé polovině šestnáctého století si ve vesnici nechal postavit Oldřich nebo Tristan Hostakovský dvoukřídlou renesanční tvrz, na které roku 1600 sídlil Jaroslav Osterský Kaplíř ze Sulevic. Spolu s vrbičanským panstvím ji zdědil syn Smil, kterému byly v roce 1623 zkonfiskovány za účast na stavovském povstání, a novým majitelem se ještě téhož roku stal apelační rada Pavel Vencelius z Bochova. Jeho dcera se provdala za Františka Karla Kressla z Kvaltenberka, který byl v roce 1693 povýšen do rytířského stavu. Okolo roku 1710 byla zahájena přestavba staré tvrze na barokní zámek podle projektu, jehož autorem byl nejspíše stavitel Octavio Broggio.

Poslední mužský člen rodu, František Karel Kressl, povýšený roku 1760 do panského stavu byl prvním ředitelem právnické fakulty v Praze. I když v Třebušíně pobýval jen zřídka, jako podporovatel první generace obrozenců a patriot, přikoupil k třebušínskému panství vrch Kalich se zříceninou stejnojmenného hradu založeného Janem Žižkou. Po smrti Františkovy manželky rodinný majetek zdědil synovec František Karel Puteani. Puteaniho manželka Antonie nechala po manželově smrti přistavět východní křídlo. Jejím potomkům zámek patřil až do roku 1906, kdy ho i hospodářským dvorem koupil Josef Haneschk. Posledním soukromým majitelem se stal roku 1913 lesník Oto J. J. Männel. Po roce 1945 v zámku vznikla škola, která v něm fungovala až do roku 1991. Později byl zámek upraven na hotel.

Stavební podoba
Starší zámecké křídlo na severní straně má obdélný půdorys. V přízemních místnostech se dochovaly křížové klenby s hřebínky. Obytné místnosti v patře byly zdobené nástěnnými malbami krajinných vedut a štuky. Autorem štuků byl Tommaso Soldati. V zámku bývala kaple. Východní křídlo bez větší architektonické hodnoty bylo postaveno roku 1860. Středem východního křídla vede průjezd do dvora, kde se pod omítkou severního křídla dochoval barokní portál s uchy a kapkami.

Odkazy

Reference

Související články
 Seznam zámků v Ústeckém kraji

Externí odkazy

 Třebušínský zámek na webu Hrady.cz

Barokní zámky v okrese Litoměřice
Kulturní památky v okrese Litoměřice
Vrbičanské panství
Třebušín
Sídla v CHKO České středohoří

redpajama_set_name: RedPajamaWikipedia


text:
TaxVox:
The voices of Tax Policy Center's researchers and staff
Elaine Maag
The IRS Could Improve EITC Compliance by Regulating Tax Preparers
Tax preparers play a critical role helping low income working families collect benefits from the Earned Income Tax Credit. Almost 60 percent of families claiming the EITC in 2010 and 2011 did so with the help of a paid preparer. Unfortunately, preparers can make costly mistakes—errors the taxpayer is ultimately responsible for resolving. The IRS could help to protect these families—and prevent some overpayments—by imposing minimum competency and qualification standards for authorized tax preparers. But first, Congress must give IRS the authority to regulate preparers, a step lawmakers say they support but have not yet taken.
The EITC provides substantial assistance to low-income working families – particularly those with children – delivering about $60 billion in benefits annually. The credit rises with income, levels off, and then eventually declines with further increases in income. The maximum benefit a family with one child can receive in 2015 is $3,359. Families with at least three children can receive up to $6,242.
Using data from its National Research Program from tax year 2009, the IRS estimates the level of overclaimed EITC payments for fiscal year 2013 was between 22 percent and 26 percent of total EITC program payments. The biggest reason: complicated qualifying child rules. And often, paid preparers made the mistakes. Lower bound estimates from an IRS compliance study showed 44 percent of EITC returns prepared by a paid preparer contained at least one error – totaling 29 percent of all the EITC payments claimed on those returns.
Today, many paid firms and individuals can claim to be qualified to file returns for others without ever meeting minimum competency standards. Some erroneous returns are produced by unscrupulous preparers hoping to inflate a client's EITC, which could, not incidentally, boost the preparer's fees. But often, preparers make mistakes because they don't fully understand the complex tax code. Regulation could help reduce those mistakes the most.
In 2010, IRS began a program designed to certify paid preparers who met minimum competency standards. But before the program could be fully implemented, an appeals court held that the IRS lacked authority to regulate some preparers. Since then, the agency and many on Capitol Hill have tried to convince Congress to give IRS power to regulate all preparers. But faced with opposition from some preparers, who argue the legislation would give the agency too much authority, the measure has stalled—most recently in the Senate Finance Committee.
Congress should act, both to help protect low-income workers from EITC errors and to strengthen the credit's integrity. But If Congress doesn't do anything, it shouldn't be surprised when it learns next year that the IRS is still overpaying credits.
Posts and comments are solely the opinion of the author and not that of the Tax Policy Center, Urban Institute, or Brookings Institution.
Individual Taxes Earned income tax credit (EITC)
low-income families
paid preparers
https://tpc.io/20btOrpShare
‹Read Previous The Case of the Questionable Tax Incentive: Women and Retirement Savings
Read Next› Bipartisan tax reform is possible: Lessons learned from President Bush's reform panel


text:
Home > Videos As DVDs, MP4 Video Downloads, MPG Videos On USB Flash Drives > History DVDs, MP4 Video Downloads, MPG Videos On USB Flash Drives > The Lost Pharaoh: The Search For Akhenaten DVD, Download, USB Drive
The Lost Pharaoh: The Search For Akhenaten DVD, Download, USB Drive
Item# the-lost-pharaoh-the-search-for-akhenaten
A Journey With A Canadian Expedition To The Valley Of The Kings In Search Of The Elusive Pharaoh Akhenaten, Ruler Of Ancient Egypt For 17 Years As Its High Priest Of His New Religion Of The Cult Of The One God Sun Disc, With Special Appearance By Omm Sety (Dorothy Eady), Keeper Of The Abydos Temple Of Seti I And Draughtswoman For The Department Of Egyptian Antiquities - Presented In The Highest DVD Quality MPG Video Format Of 9.1 MBPS As An Archival Quality All Regions Format DVD, MP4 Video Download Or USB Flash Drive! (Color, 1990, 45 Minutes.) #TheLostPharaoh #Akhenaten #Echnaton #Akhenaton #Ikhnaton #Khuenaten #Aten #Atenism #AmenhotepIV #EighteenthDynastyOfEgypt #NewKingdomOfEgypt #Egyptology #Egypt #EgyptianHistory #AncientEgypt #AncientEgyptianHistory #Archeology #Archaeology #Monotheism #OmmSety #OmSeti #DorothyEady #FlindersPetrie #DVD #VideoDownload #MP4 #USBFlashDrive
Akhenaten, also spelled Echnaton, Akhenaton, Ikhnaton, and Khuenaten (Ancient Egyptian: "Effective For The Aten"), was an ancient Egyptian pharaoh reigning c._1353-1336 or 1351-1334 BC, the tenth ruler of the Eighteenth Dynasty. Before the fifth year of his reign, he was known as Amenhotep IV (Ancient Egyptian: jmn-htp, meaning "Amun is satisfied", Hellenized as Amenophis IV). As a pharaoh, Akhenaten is noted for abandoning Egypt's traditional polytheism and introducing Atenism, or worship centered around Aten. The views of Egyptologists differ as to whether Atenism should be considered as a form of absolute monotheism, or whether it was monolatry, syncretism, or henotheism. This culture shift away from traditional religion was not widely accepted. After his death, Akhenaten's monuments were dismantled and hidden, his statues were destroyed, and his name excluded from lists of rulers compiled by later pharaohs. Traditional religious practice was gradually restored, notably under his close successor Tutankhamun, who changed his name from Tutankhaten early in his reign. When some dozen years later, rulers without clear rights of succession from the Eighteenth Dynasty founded a new dynasty, they discredited Akhenaten and his immediate successors and referred to Akhenaten as "the enemy" or "that criminal" in archival records. Akhenaten was all but lost to history until the late 19th century discovery of Amarna, or Akhetaten, the new capital city he built for the worship of Aten. Furthermore, in 1907, a mummy that could be Akhenaten's was unearthed from the tomb KV55 in the Valley of the Kings by Edward R. Ayrton. Genetic testing has determined that the man buried in KV55 was Tutankhamun's father, but its identification as Akhenaten has since been questioned. Akhenaten's rediscovery and Flinders Petrie's early excavations at Amarna sparked great public interest in the pharaoh and his queen Nefertiti. He has been described as "enigmatic", "mysterious", "revolutionary", "the greatest idealist of the world", and "the first individual in history", but also as a "heretic", "fanatic", "possibly insane", and "mad". The interest comes from his connection with Tutankhamun, the unique style and high quality of the pictorial arts he patronized, and ongoing interest in the religion he attempted to establish.