research28 min studyLesson 933 in Engineering

Search the feasible region without drifting out of it

Implement projected iterative loss ascent with original-input constraints, best-candidate tracking, and reproducible restarts.

On this page

What you’ll understand

  • Compute an infinity-ball and box projection step.
  • Explain how restarts strengthen empirical search without certifying it.
  • Preserve attack successes and compare resource budgets honestly.

A single gradient step commits to the local direction at one input. Iterative projected attacks recompute that direction after each move while enforcing a fixed feasible set around the original example. Randomized restarts inspect different initial points because nonlinear losses may have several useful regions. These mechanisms make a more serious robustness test, but the inner maximization remains approximate. The implementation should make its search budget and candidate history auditable so a stronger run cannot accidentally discard a failure that an earlier iterate already found.

Project around the original input

For an infinity-ball image threat, the feasible coordinate interval is the intersection of the original pixel’s epsilon interval with the legal image box. Clip each proposed iterate to those fixed bounds. Clipping only into [0,1] enforces image validity but allows repeated steps to exceed the total threat budget. Clipping around the previous iterate enforces a per-step budget and has the same drift problem. The clean original tensor must remain available and unchanged throughout the run.

Euclidean projection uses a radial rescaling for a norm ball, whereas an additional box intersection needs care. A sequential ball projection and box clipping can produce a feasible point for a box containing the original image, but should not be described automatically as the exact Euclidean projection onto the intersection. The optimization method and any approximation should be stated. Feasibility and exact projection optimality are different properties, and only the former is required to validate a found counterexample.

zk+1,j=min⁡{uj,max⁡{lj,zk,j+η sign⁡(∇zℓ)j}},lj=max⁡(0,xj−ε),uj=min⁡(1,xj+ε)z_{k+1,j}=\min\{u_j,\max\{l_j,z_{k,j}+\eta\,\operatorname{sign}(\nabla_z\ell)_j\}\},\quad l_j=\max(0,x_j-\varepsilon),\quad u_j=\min(1,x_j+\varepsilon)
x is the fixed original input in [0,1]^d, z_k a feasible iterate, ε≥0 the total infinity budget, and η>0 a per-step coordinate change in input units. The gradient is evaluated at z_k through the specified model.↔ Scroll wide equations horizontally.

Preserve failures and explore starting points

Initialize each restart using a documented distribution over feasible points, and record its seed. Uniform sampling in an infinity box is straightforward before accounting for clipping at the image boundary; clipping a larger random box does not generally yield a uniform sample from the final intersection. Uniformity is not required for a valid attack, but the actual initialization law should be described accurately. Include the clean start as a useful reference when comparing restart policies.

Track the strongest relevant candidate across every iterate and restart. For deterministic untargeted classification, once a valid candidate is misclassified, preserve that success even if later steps return to the correct class. A maximum-loss candidate and a successful candidate need not be identical when a surrogate ranks them differently. Reevaluate saved candidates through the final wrapper. Adding restarts should not increase reported survival when earlier candidates and the same success definition are retained.

CK,R={x}∪{zk,r:0≤k≤K, 1≤r≤R},fail⁡(x)=max⁡z∈CK,R1{F(z)≠y}\mathcal C_{K,R}=\{x\}\cup\{z_{k,r}:0\leq k\leq K,\ 1\leq r\leq R\},\qquad \operatorname{fail}(x)=\max_{z\in\mathcal C_{K,R}}\mathbf1\{F(z)\ne y\}
This finite candidate set is checked for feasibility before success aggregation. K is an iteration count and R a restart count. For stochastic classifiers, the indicator must be replaced by the explicitly defined repeated-evaluation success procedure.↔ Scroll wide equations horizontally.

Treat convergence plots as diagnostics

Sweep step size, iteration count, loss formulation, and restart count on development examples while keeping the final evaluation protocol fixed. A large step may bounce across a narrow useful region; a tiny step may barely move within the allowed runtime. Plot best-so-far loss and cumulative valid failures rather than only final loss. Flat curves can indicate convergence, poor gradients, numerical saturation, or a broken constraint implementation, so they are not independently a robustness argument.

Budget comparisons should count actual model evaluations and backward passes, not only an iteration label. A restart with many gradient samples per step costs more than a deterministic single-gradient run. Report wall time and hardware as additional practical measurements. Retain per-example traces or sufficient summaries to inspect a sudden increase in survival after a code change. A seemingly stronger configuration that finds fewer failures deserves investigation before its result becomes a claimed defense improvement.

Two projected steps at an image boundary

Let x=(0.9,0.2), total infinity budget ε=0.15, and step size η=0.1. Start at x and assume gradient signs remain (+,−). Compute two iterative steps using fixed original-input bounds.

  1. The feasible lower bounds are (0.75,0.05) and upper bounds are (1,0.35). They remain fixed for both steps because the original input remains (0.9,0.2).

  2. The first proposal is (1.0,0.1), already feasible, so z₁=(1.0,0.1). Its displacement from x is (0.1,−0.1).

  3. The second proposal is (1.1,0), which projects to z₂=(1,0.05). Its displacement is (0.1,−0.15), giving infinity norm exactly 0.15 and satisfying both constraints.

The result

The second raw proposal exceeds both a domain boundary and the allowed displacement. Fixed-bound projection returns a valid candidate without turning the total epsilon into a per-step allowance.

Explore the model

Interactive lab

Interactive lab · optimization

Inspect step-size behavior in a simple iterative model

Reset, set Step size η to 1.5 and Initial position x₀ to 2. Predict x₁=−1 and x₂=0.5 after two successive Steps. Reset, explicitly set η=2.5 and x₀=2, then take two Steps: predict x₁=−3 and x₂=4.5, with an out-of-plot report. This instrument performs descent on x²/2 without projection; it illustrates step-size sensitivity, not PGD attack ascent or neural loss geometry.

Inspect step-size behavior in a simple iterative modelGradient descent on f(x) = x²/2: xₙ = (1 − η)ⁿx₀. Playback advances two discrete iterations per second. Values outside |x| ≤ 4 are explicitly reported. Current readings: Position x0: 2; Objective x²/2: 2; Iteration behavior: Stable step. All parameters are adjustable with the labeled controls below.−4−202402.174.356.528.7Parameter xf(x) = x²/2n = 0
ObjectiveDiscrete iterate
Position x0
2
Objective x²/2
2
Iteration behavior
Stable step
n = 0 · t = 0 s

Gradient descent on f(x) = x²/2: xₙ = (1 − η)ⁿx₀. Playback advances two discrete iterations per second. Values outside |x| ≤ 4 are explicitly reported. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.

Look forAn iteration count has little meaning without the update rule and step-size regime.

Check your understanding

Which change can incorrectly let a multi-step attack exceed its stated total infinity budget?

Try it yourself

Three restarts find valid failures on sets {1,2,3}, {3,4}, and {2,5} among ten initially correct examples. What is attack-survival accuracy after preserving the union? Can it be computed by averaging the restart failure counts?

Take a moment to make a prediction or work it out on paper. Open a hint when you need one.

Give me a hint

List distinct failed example IDs once.

Compare with the solution

The union is {1,2,3,4,5}, so five examples fail and survival accuracy is 5/10=50 percent. Averaging counts 3,2,2 loses overlap information and does not give the cumulative worst-case result. This 50 percent remains an empirical upper bound on exact finite-set robust accuracy under the stated feasible search.

Take it with you

  • Keep every projected iterate within a fixed original-input feasible set.
  • Preserve successful candidates across steps, restarts, and attack variants.
  • Report actual search resources and treat plateaus as diagnostic evidence.

Read further

Original sources and deeper explanations to follow at your own pace.

Optional progress, saved in this browser when available. Revisit any lesson at any time.

Lesson not marked complete.